On the existence of subexponential parameterized algorithms

DOI10.1016/S0022-0000(03)00074-6zbMath1091.68121MaRDI QIDQ1877709

David W. Juedes, Li-Ming Cai

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Parameterized algorithms for feedback set problems and their duals in tournaments, Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width, (Total) vector domination for graphs with bounded branchwidth, Fixed-parameter approximation: conceptual framework and approximability results, Vertex Cover, Dominating Set and My Encounters with Parameterized Complexity and Mike Fellows, A Basic Parameterized Complexity Primer, Parameterized Complexity and Subexponential-Time Computability, Graph Minors and Parameterized Algorithm Design, Genus characterizes the complexity of certain graph problems: Some tight results, Unnamed Item, Component order connectivity in directed graphs, Unnamed Item, A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion, Hitting forbidden subgraphs in graphs of bounded treewidth, An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion, Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Parameterized approximation via fidelity preserving transformations, On the parameterized vertex cover problem for graphs with perfect matching, Parameterized and subexponential-time complexity of satisfiability problems and applications, Solving vertex cover in polynomial time on hyperbolic random graphs, Subexponential parameterized algorithms, Confronting intractability via parameters, The Constant Inapproximability of the Parameterized Dominating Set Problem, \textsc{Max-Cut} parameterized above the Edwards-Erdős bound, Subexponential fixed-parameter algorithms for partial vector domination, Structure of polynomial-time approximation, Kernels in planar digraphs, Slightly Superexponential Parameterized Problems, Improved upper bounds for vertex cover, Component order connectivity in directed graphs, Exact algorithms for the Hamiltonian cycle problem in planar graphs, On the computational hardness based on linear fpt-reductions, Approximability of clique transversal in perfect graphs, Large Independent Sets in Subquartic Planar Graphs, Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}, On parameterized exponential time complexity, Kernelization: New Upper and Lower Bound Techniques, Dynamic programming for graphs on surfaces, Tight lower bounds for certain parameterized NP-hard problems, Parameterized Algorithms for Generalized Domination, Parameterized computation and complexity: a new approach dealing with NP-hardness, On subexponential and FPT-time inapproximability, Faster parameterized algorithms for deletion to split graphs, A technique for obtaining true approximations for \(k\)-center with covering constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved fixed-parameter algorithm for vertex cover
• Optimization, approximation, and complexity classes
• Some simplified NP-complete graph problems
• On fixed-parameter tractability and approximability of NP optimization problems
• Which problems have strongly exponential complexity?
• A general method to speed up fixed-parameter-tractable algorithms
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• On the structure of parameterized problems in NP
• Vertex Cover: Further Observations and Further Improvements
• Vertex packings: Structural properties and algorithms
• Nondeterminism within $P^ * $
• The Complexity of Decision Versus Search
• Circuit Bottom Fan-in and Computational Power
• Faster exact algorithms for hard problems: A parameterized point of view