Strong computational lower bounds via parameterized complexity
From MaRDI portal
Publication:856413
DOI10.1016/J.JCSS.2006.04.007zbMATH Open1119.68092OpenAlexW2130190334WikidataQ55891718 ScholiaQ55891718MaRDI QIDQ856413FDOQ856413
Ge Xia, Xiuzhen Huang, Iyad Kanj, Jianer Chen
Publication date: 7 December 2006
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2006.04.007
computational complexitylower boundcliqueparameterized computationpolynomial time approximation scheme
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Which problems have strongly exponential complexity?
- Genetic Design of Drugs Without Side-Effects
- Fundamentals of Computation Theory
- Matrix multiplication via arithmetic progressions
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Vertex packings: Structural properties and algorithms
- Characterizing parallel hierarchies by reducibilities
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- On limited nondeterminism and the complexity of the V-C dimension
- Algorithms for maximum independent sets
- Vertex cover: Further observations and further improvements
- Tight lower bounds for certain parameterized NP-hard problems
- Solving large FPT problems on coarse-grained parallel machines
- Finding a Maximum Independent Set
- On the complexity of database queries
- An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
Cited In (93)
- Deciding Parity Games in Quasi-polynomial Time
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- Title not available (Why is that?)
- Characterizing polynomial Ramsey quantifiers
- Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
- Counting Small Induced Subgraphs with Hereditary Properties
- Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
- Quasipolynomiality of the Smallest Missing Induced Subgraph
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Logical complexity of induced subgraph isomorphism for certain families of graphs
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Counting subgraphs in somewhere dense graphs
- Iterated lower bound formulas: a diagonalization-based approach to proof complexity
- Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
- Obtaining a proportional allocation by deleting items
- The complexity of pattern counting in directed graphs, parameterised by the outdegree
- Parameterized complexity of computing maximum minimal blocking and hitting sets
- Maximum locally irregular induced subgraphs via minimum irregulators
- Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier
- Sum-of-Products with Default Values: Algorithms and Complexity Results
- Backdoor Sets for CSP.
- Pattern masking for dictionary matching: theory and practice
- Parameterised and fine-grained subgraph counting, modulo 2
- A multistage view on 2-satisfiability
- Parameterized Complexity and Subexponential-Time Computability
- An improved lower bound on approximation algorithms for the closest substring problem
- Counting induced subgraphs: an algebraic approach to \(\#\)W[1]-hardness
- Grundy Coloring and friends, half-graphs, bicliques
- Title not available (Why is that?)
- On the independent set problem in random graphs
- Strong time bounds: Non-computable bounds and a hierarchy theorem
- On the Variable Hierarchy of First-Order Spectra
- The union of minimal hitting sets: parameterized combinatorial bounds and counting
- The descriptive complexity of subgraph isomorphism without numerics
- The complexity of dependency detection and discovery in relational databases
- Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- Counting Small Induced Subgraphs Satisfying Monotone Properties
- A second step toward the strong polynomial-time hierarchy
- Calculation of Discrepancy Measures and Applications
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- A Dichotomy Result for Ramsey Quantifiers
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- On the complexity of connection games
- Known Algorithms for Edge Clique Cover are Probably Optimal
- On the pseudo-achromatic number problem
- Parameterized counting of partially injective homomorphisms
- Parameterized complexity of firefighting
- Kernelization: New Upper and Lower Bound Techniques
- From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability
- Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications
- Subset feedback vertex set on graphs of bounded independent set size
- Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
- A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computing the depth distribution of a set of boxes
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- On parameterized exponential time complexity
- Distance-Based Clique Relaxations in Networks: s-Clique and s-Club
- Ruling out FPT algorithms for weighted coloring on forests
- Parameterized shifted combinatorial optimization
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Half-integrality, LP-branching, and FPT algorithms
- Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width
- On the Pseudo-achromatic Number Problem
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Faster algorithms for counting subgraphs in sparse graphs
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- Parameterized Counting and Cayley Graph Expanders
- Safe Approximation and Its Relation to Kernelization
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
- Refining complexity analyses in planning by exploiting the exponential time hypothesis
- Lower bounds for the happy coloring problems
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
- A tight lower bound for planar Steiner orientation
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- On subexponential and FPT-time inapproximability
- Lower Bounds for the Graph Homomorphism Problem
- Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
- A spectral algorithm for finding maximum cliques in dense random intersection graphs
- On the Complexity of Bounded Context Switching.
- Title not available (Why is that?)
- An initial study of time complexity in infinite-domain constraint satisfaction
- Genus characterizes the complexity of certain graph problems: Some tight results
- Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Twin-width and polynomial kernels
- On first-order definitions of subgraph isomorphism properties
- A tight algorithm for strongly connected Steiner subgraph on two terminals with demands
- Maximum cliques in graphs with small intersection number and random intersection graphs
This page was built for publication: Strong computational lower bounds via parameterized complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q856413)
