Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
From MaRDI portal
Publication:1892937
DOI10.1016/0168-0072(94)00034-ZzbMath0828.68077DBLPjournals/apal/AbrahamsonDF95WikidataQ56620260 ScholiaQ56620260MaRDI QIDQ1892937
Karl A. Abrahamson, Michael R. Fellows, Rodney G. Downey
Publication date: 26 July 1995
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (59)
Tractability in constraint satisfaction problems: a survey ⋮ Describing parameterized complexity classes ⋮ The Turing way to parameterized complexity ⋮ On the existence of subexponential parameterized algorithms ⋮ A parameterized complexity view on collapsing \(k\)-cores ⋮ Compactors for parameterized counting problems ⋮ A Retrospective on (Meta) Kernelization ⋮ On the efficiency of polynomial time approximation schemes ⋮ On variants of vertex geography on undirected graphs ⋮ Parameterized power domination complexity ⋮ The Birth and Early Years of Parameterized Complexity ⋮ A Basic Parameterized Complexity Primer ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ Bounded fixed-parameter tractability and reducibility ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Strong computational lower bounds via parameterized complexity ⋮ On fixed-parameter tractability and approximability of NP optimization problems ⋮ Backdoor sets for DLL subsolvers ⋮ \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling] ⋮ Parameterized pursuit-evasion games ⋮ Parameterized circuit complexity and the \(W\) hierarchy ⋮ Tractability, hardness, and kernelization lower bound for and/or graph solution ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ Deciding the winner in \(k\) rounds for DISJOINT ARROWS, a new combinatorial partizan game ⋮ Fixed-parameter decidability: Extending parameterized complexity analysis ⋮ On bounded block decomposition problems for under-specified systems of equations ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ The parameterized complexity of stabbing rectangles ⋮ The complexity of the asynchronous prediction of the majority automata ⋮ Unnamed Item ⋮ On structural parameterizations of Node Kayles ⋮ Unnamed Item ⋮ Treewidth governs the complexity of target set selection ⋮ Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms ⋮ Confronting intractability via parameters ⋮ Efficient algorithms for counting parameterized list \(H\)-colorings ⋮ Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey ⋮ Fixed-parameter tractability and completeness II: On completeness for W[1] ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ Advice classes of parametrized tractability ⋮ W-hierarchies defined by symmetric gates ⋮ On some tractable and hard instances for partial incentives and target set selection ⋮ The intractability of computing the Hamming distance ⋮ The parameterized complexity of editing graphs for bounded degeneracy ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack ⋮ Unnamed Item ⋮ Threshold dominating sets and an improved characterization of \(W[2\)] ⋮ Parameterized Complexity of Discrete Morse Theory ⋮ Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers ⋮ Parameterized Complexity ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Sparse parameterized problems ⋮ Tight lower bounds for certain parameterized NP-hard problems ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ On the complexity of database queries ⋮ Preprocessing of intractable problems ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits ⋮ Which problems have strongly exponential complexity?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Advice classes of parametrized tractability
- Graph minors. XX: Wagner's conjecture
- Parameterized circuit complexity and the \(W\) hierarchy
- On the complexity of some two-person perfect-information games
- Graph minors. XIII: The disjoint paths problem
- Beyond NP-completeness for problems of bounded width (extended abstract)
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Planar Formulae and Their Uses
- A Combinatorial Problem Which Is Complete in Polynomial Space
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Nondeterminism within $P^ * $
- Fixed-Parameter Tractability and Completeness I: Basic Results
This page was built for publication: Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
