FPT is characterized by useful obstruction sets
From MaRDI portal
Publication:2828222
DOI10.1145/2635820zbMath1347.68167OpenAlexW2034472295WikidataQ57359585 ScholiaQ57359585MaRDI QIDQ2828222
Michael R. Fellows, Bart M. P. Jansen
Publication date: 24 October 2016
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2635820
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
New Limits to Classical and Quantum Instance Compression ⋮ Sparsification upper and lower bounds for graph problems and not-all-equal SAT ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Minor obstructions for apex-pseudoforests
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Data reduction for graph coloring problems
- Outerplanar obstructions for a feedback vertex set
- Forbidden graphs for tree-depth
- Infeasibility of instance compression and succinct PCPs for NP
- Graph minors. XX: Wagner's conjecture
- Some consequences of non-uniform conditions on uniform classes
- On the size of minimal unsatisfiable formulas
- On problems without polynomial kernels
- Graph minors. I. Excluding a forest
- Graph minors. V. Excluding a planar graph
- The vertex separation number of a graph equals its path-width
- Upper bounds on the size of obstructions and intertwines
- A partial k-arboretum of graphs with bounded treewidth
- Minimal acyclic forbidden minors for the family of graphs with bounded path-width
- On computing graph minor obstruction sets
- Graph minors. XIII: The disjoint paths problem
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- On sparsification for computing treewidth
- Properties of vertex cover obstructions
- Crown structures for vertex cover kernelization
- Vertex Cover: Further Observations and Further Improvements
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Kernel Bounds for Structural Parameterizations of Pathwidth
- Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs
- Kernelization – Preprocessing with a Guarantee
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Kernelization: New Upper and Lower Bound Techniques
- Complexity of Finding Embeddings in a k-Tree
- Nonconstructive tools for proving polynomial-time decidability
- The Pathwidth and Treewidth of Cographs
- Minor‐order obstructions for the graphs of vertex cover 6
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- Co-Nondeterminism in Compositions
- (Meta) Kernelization
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Forbidden minors to graphs with small feedback sets
This page was built for publication: FPT is characterized by useful obstruction sets
