Advice classes of parametrized tractability
From MaRDI portal
Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parametrized problems that can be solved (uniformly with respect to the parameter) in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it is shown that the class FPT of tractable parameterized problems (the parametrized analog of P) has interesting and natural internal structure.
Recommendations
- Corrigendum to: ``Advice classes of parameterized tractability
- The structure of logarithmic advice complexity classes
- Bounding the complexity of advice functions
- The advice complexity of a class of hard online problems
- Advice complexity for a class of online problems
- Nondeterministic Instance Complexity and Proof Systems with Advice
- Advice Automatic Structures and Uniformly Automatic Classes
- Complexity-Restricted Advice Functions
- Advice complexity and barely random algorithms
- Advice complexity and barely random algorithms
Cites work
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XX: Wagner's conjecture
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- scientific article; zbMATH DE number 4051026 (Why is no real title available?)
- scientific article; zbMATH DE number 47903 (Why is no real title available?)
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- scientific article; zbMATH DE number 140499 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 475614 (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 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 219251 (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 Covering Vertices by Faces in a Planar Graph
- On the parameterized complexity of short computation and factorization
- Two strikes against perfect phylogeny
- Word Problems Solvable in Logspace
Cited in
(46)- On problems without polynomial kernels
- The structure of logarithmic advice complexity classes
- A general method to speed up fixed-parameter-tractable algorithms
- Corrigendum to: ``Advice classes of parameterized tractability
- On the parametric complexity of schedules to minimize tardy tasks.
- Describing parameterized complexity classes
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
- Approximation in (poly-) logarithmic space
- Parameterized analysis and crossing minimization problems
- On the space and circuit complexity of parameterized problems: classes and completeness
- The parameterized space complexity of embedding along a path
- Kernels in planar digraphs
- A parametric analysis of the state-explosion problem in model checking
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- The birth and early years of parameterized complexity
- Studies in Computational Aspects of Voting
- A shortcut to (sun)flowers: kernels in logarithmic space or linear time
- Win-win kernelization for degree sequence completion problems
- Surfing with Rod
- Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
- Computing Hitting Set Kernels By AC^0-Circuits
- New limits to classical and quantum instance compression
- Kernelization: new upper and lower bound techniques
- Incremental list coloring of graphs, parameterized by conservation
- Finding points in general position
- Fractals for kernelization lower bounds
- Computing kernels in parallel: lower and upper bounds
- Approximation in (Poly-) Logarithmic Space
- Advice Automatic Structures and Uniformly Automatic Classes
- Parameterized complexity of critical node cuts
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Faster existential FO model checking on posets
- What Is Known About Vertex Cover Kernelization?
- Infeasibility of instance compression and succinct PCPs for NP
- On the parallel parameterized complexity of MaxSAT variants
- Space-efficient graph kernelizations
- Parameterized complexity of shortest path with positive disjunctive constraints
- Kernelization of counting problems
- Scheduling kernels via configuration LP
- Semantic tree-width and path-width of conjunctive regular path queries
- Kernelization complexity of solution discovery problems
- On the polynomial kernelizations of finding a shortest path with positive disjunctive constraints
- On kernelization with access to NP-oracles
- (Almost-)optimal FPT algorithm and kernel for T-cycle on planar graphs
- The complexity of degree anonymization by vertex addition
This page was built for publication: Advice classes of parametrized tractability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676315)
