Strong computational lower bounds via parameterized complexity

DOI10.1016/j.jcss.2006.04.007zbMath1119.68092OpenAlexW2130190334WikidataQ55891718 ScholiaQ55891718MaRDI QIDQ856413

Ge Xia, Xiuzhen Huang, Iyad A. Kanj, Jian'er 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

zbMATH Keywords

computational complexity lower bound clique parameterized computation polynomial time approximation scheme

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (84)

Maximum cliques in graphs with small intersection number and random intersection graphs ⋮ On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Safe Approximation and Its Relation to Kernelization ⋮ Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ On the complexity of connection games ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ On the Pseudo-achromatic Number Problem ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ Genus characterizes the complexity of certain graph problems: Some tight results ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Sum-of-Products with Default Values: Algorithms and Complexity Results ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract) ⋮ A Dichotomy Result for Ramsey Quantifiers ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ A spectral algorithm for finding maximum cliques in dense random intersection graphs ⋮ On the Variable Hierarchy of First-Order Spectra ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ Parameterized complexity of computing maximum minimal blocking and hitting sets ⋮ Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ A multistage view on 2-satisfiability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ Characterizing polynomial Ramsey quantifiers ⋮ Backdoor Sets for CSP. ⋮ Parameterized complexity of firefighting ⋮ Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ Refining complexity analyses in planning by exploiting the exponential time hypothesis ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ On first-order definitions of subgraph isomorphism properties ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ A tight algorithm for strongly connected Steiner subgraph on two terminals with demands ⋮ Unnamed Item ⋮ A tight lower bound for planar Steiner orientation ⋮ An improved lower bound on approximation algorithms for the closest substring problem ⋮ Computing vertex-surjective homomorphisms to partially reflexive trees ⋮ Parameterized shifted combinatorial optimization ⋮ Unnamed Item ⋮ Ruling out FPT algorithms for weighted coloring on forests ⋮ Parameterized counting of partially injective homomorphisms ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ On the independent set problem in random graphs ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ On the pseudo-achromatic number problem ⋮ Unnamed Item ⋮ Obtaining a proportional allocation by deleting items ⋮ Lower bounds for the happy coloring problems ⋮ Computing the depth distribution of a set of boxes ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ The complexity of dependency detection and discovery in relational databases ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ On parameterized exponential time complexity ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ The union of minimal hitting sets: parameterized combinatorial bounds and counting ⋮ On the Complexity of Bounded Context Switching. ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness] ⋮ Logical complexity of induced subgraph isomorphism for certain families of graphs ⋮ Twin-width and polynomial kernels ⋮ On subexponential and FPT-time inapproximability ⋮ Calculation of Discrepancy Measures and Applications

Cites Work

This page was built for publication: Strong computational lower bounds via parameterized complexity