Hitting Forbidden Minors: Approximation and Kernelization
From MaRDI portal
Publication:2790404
DOI10.1137/140997889zbMath1336.68123OpenAlexW1787689584WikidataQ60488375 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
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
