Tight lower bounds for certain parameterized NP-hard problems

DOI10.1016/j.ic.2005.05.001zbMath1161.68476OpenAlexW2009147258WikidataQ57360004 ScholiaQ57360004MaRDI QIDQ2568440

Michael R. Fellows, Xiuzhen Huang, Benny Chor, Ge Xia, David W. Juedes, Iyad A. Kanj, Jian'er Chen

Publication date: 10 October 2005

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2005.05.001

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (78)

Parameterized graph separation problems ⋮ On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases ⋮ On the parameterized complexity of \(d\)-dimensional point set pattern matching ⋮ A Basic Parameterized Complexity Primer ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ Genus characterizes the complexity of certain graph problems: Some tight results ⋮ Strong computational lower bounds via parameterized complexity ⋮ On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Courcelle's theorem for triangulations ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Paradigms for parameterized enumeration ⋮ Fixed-parameter tractability and lower bounds for stabbing problems ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ A Dichotomy Result for Ramsey Quantifiers ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ Unnamed Item ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ Editing graphs to satisfy degree constraints: a parameterized approach ⋮ Exploiting hidden structure in selecting dimensions that distinguish vectors ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ The parameterized complexity of stabbing rectangles ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized two-player Nash equilibrium ⋮ Local search for string problems: brute-force is essentially optimal ⋮ Unnamed Item ⋮ Tight Hardness Results for Consensus Problems on Circular Strings and Time Series ⋮ Characterizing polynomial Ramsey quantifiers ⋮ Treewidth governs the complexity of target set selection ⋮ Searching the \(k\)-change neighborhood for TSP is W[1-hard] ⋮ Confronting intractability via parameters ⋮ Backdoors for linear temporal logic ⋮ Single Parameter FPT-Algorithms for Non-trivial Games ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Monitoring the edges of a graph using distances ⋮ Refining complexity analyses in planning by exploiting the exponential time hypothesis ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two ⋮ On the computational hardness based on linear fpt-reductions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized counting of partially injective homomorphisms ⋮ The complexity ecology of parameters: An illustration using bounded max leaf number ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Lower bounds for the happy coloring problems ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ Computing the depth distribution of a set of boxes ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Strong Backdoors for Default Logic ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ On parameterized exponential time complexity ⋮ On problems without polynomial kernels ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness] ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Fixed-parameter complexity and approximability of norm maximization ⋮ On structural parameterizations for the 2-club problem ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters ⋮ Calculation of Discrepancy Measures and Applications ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

Cites Work

This page was built for publication: Tight lower bounds for certain parameterized NP-hard problems