Hitting Forbidden Minors: Approximation and Kernelization
From MaRDI portal
Publication:2790404
DOI10.1137/140997889zbMath1336.68123DBLPjournals/siamdm/FominLMPS16OpenAlexW1787689584WikidataQ60488375 ScholiaQ60488375MaRDI QIDQ2790404
Daniel Lokshtanov, Neeldhara Misra, Fedor V. Fomin, Geevarghese Philip, Saket Saurabh
Publication date: 4 March 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2011/3010/
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (17)
Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ An improved deterministic parameterized algorithm for cactus vertex deletion ⋮ Scattered packings of cycles ⋮ On the kernelization of split graph problems ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Lower bounds for protrusion replacement by counting equivalence classes ⋮ Quick but odd growth of cacti ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ Unnamed Item ⋮ Subset feedback vertex set in chordal and split graphs ⋮ Modification to Planarity is Fixed Parameter Tractable ⋮ Packing and Covering Induced Subdivisions ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monadic second-order evaluations on tree-decomposable graphs
- Looking at the stars
- On problems without polynomial kernels
- The node-deletion problem for hereditary properties is NP-complete
- Unit disk graphs
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Quickly excluding a planar graph
- Treewidth. Computations and approximations
- On the solution of linear recurrence equations
- Reduction algorithms for graphs of small treewidth
- Graph minors. XIII: The disjoint paths problem
- Approximation properties of NP minimization classes
- Crown structures for vertex cover kernelization
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Vertex Cover: Further Observations and Further Improvements
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- A 4 k 2 kernel for feedback vertex set
- Excluded Grid Theorem
- An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion
- Easy problems for tree-decomposable graphs
- Uniform Kernelization Complexity of Hitting Forbidden Minors
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- Hitting Diamonds and Growing Cacti
- A Cubic Kernel for Feedback Vertex Set
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Kernelization: New Upper and Lower Bound Techniques
- Nonconstructive tools for proving polynomial-time decidability
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- An algebraic theory of graph reduction
- Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
- The approximation of maximum subgraph problems
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Properties of vertex packing and independence system polyhedra
- Reducibility among Combinatorial Problems
- (Meta) Kernelization
- Polynomial bounds for the grid-minor theorem
- Parameterized and Exact Computation
- On Independent Circuits Contained in a Graph
- Polynomial Kernelizations For MIN F+Pi1 And MAX NP
- Bidimensionality and Geometric Graphs
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Hitting Forbidden Minors: Approximation and Kernelization
