Fixed-parameter tractability and completeness. IV: On completeness for W[ P] and PSPACE analogues
From MaRDI portal
Publication:1892937
The paper devices some new results in parametrized complexity theory. In particular, it is proved that a number of concrete hardness results for W[P], the top level of the hardness hierarchy introduced by Downey and Fellows in a series of earlier papers. This hierarchy for fixed-parameter problems is based on the logical depth needed to describe the respective problem in terms of circuits. Furthermore, analogs of PSPACE are studied in the fixed-parameter setting. This is done via certain problems concerning \(k\)-move games. Several aspects of the structural complexity of W[P] and related classes are studied. The class W[P] is characterized in terms of DTIME \((2^{o(n)})\) and NP.
Recommendations
Cites work
- A Combinatorial Problem Which Is Complete in Polynomial Space
- Advice classes of parametrized tractability
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XX: Wagner's conjecture
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 503190 (Why is no real title available?)
- scientific article; zbMATH DE number 512804 (Why is no real title available?)
- scientific article; zbMATH DE number 512844 (Why is no real title available?)
- scientific article; zbMATH DE number 1499087 (Why is no real title available?)
- scientific article; zbMATH DE number 749922 (Why is no real title available?)
- scientific article; zbMATH DE number 806748 (Why is no real title available?)
- Nondeterminism within $P^ * $
- On the complexity of some two-person perfect-information games
- Parameterized circuit complexity and the \(W\) hierarchy
- Planar Formulae and Their Uses
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- The Rectilinear Steiner Tree Problem is NP-Complete
Cited in
(71)- Parameterized circuit complexity and the \(W\) hierarchy
- Threshold dominating sets and an improved characterization of \(W[2]\)
- On the complexity of database queries
- On fixed-parameter tractability and approximability of NP optimization problems
- Which problems have strongly exponential complexity?
- On variants of vertex geography on undirected graphs
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey
- Preprocessing of intractable problems
- Describing parameterized complexity classes
- The Turing way to parameterized complexity
- On the existence of subexponential parameterized algorithms
- \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
- On some tractable and hard instances for partial incentives and target set selection
- From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability
- The complexity of the asynchronous prediction of the majority automata
- Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
- A completeness theory for polynomial (Turing) kernelization
- On the space and circuit complexity of parameterized problems: classes and completeness
- Bounded fixed-parameter tractability and reducibility
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- The parameterized complexity of stabbing rectangles
- Algorithms in the W-hierarchy
- Sparse parameterized problems
- Tight lower bounds for certain parameterized NP-hard problems
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- Solving target set selection with bounded thresholds faster than \(2^n\)
- On structural parameterizations of Node Kayles
- Tractability in constraint satisfaction problems: a survey
- Parameterized complexity: the main ideas and connections to practical computing
- Completeness results for parameterized space classes
- On the efficiency of polynomial time approximation schemes
- The birth and early years of parameterized complexity
- A basic parameterized complexity primer
- Parameterized complexity and subexponential-time computability
- Fixed-parameter decidability: extending parameterized complexity analysis
- Parameterized Chess
- Kernelization: new upper and lower bound techniques
- Deciding the winner in \(k\) rounds for DISJOINT ARROWS, a new combinatorial partizan game
- On bounded block decomposition problems for under-specified systems of equations
- Treewidth governs the complexity of target set selection
- Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms
- Confronting intractability via parameters
- scientific article; zbMATH DE number 2086399 (Why is no real title available?)
- A parameterized complexity view on collapsing \(k\)-cores
- Solving target set selection with bounded thresholds faster than \(2^n\)
- A Retrospective on (Meta) Kernelization
- Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
- Relativization and interactive proof systems in parameterized complexity theory
- An analysis of the W*-hierarchy
- The intractability of computing the Hamming distance
- Machine-based methods in parameterized complexity theory
- Parameterized pursuit-evasion games
- scientific article; zbMATH DE number 7764095 (Why is no real title available?)
- Complexity of maker-breaker games on edge sets of graphs
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Advice classes of parametrized tractability
- Bicriteria \textsf{FPT}-approximation algorithms for vertex deletion to bounded degeneracy graphs
- On the computational complexity of graph reconstruction
- FPT approximation using treewidth: capacitated vertex cover, target set selection and vector dominating set
- On the complexity of problems on tree-structured graphs
- Bicriteria FPT-approximation algorithms for vertex deletion to bounded degeneracy graphs
- A parameterized complexity view on collapsing \(k\)-cores
- Compactors for parameterized counting problems
- Parameterized power domination complexity
- Strong computational lower bounds via parameterized complexity
- Backdoor sets for DLL subsolvers
- Efficient algorithms for counting parameterized list H-colorings
- W-hierarchies defined by symmetric gates
- The parameterized complexity of editing graphs for bounded degeneracy
This page was built for publication: Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892937)
