A 4 k 2 kernel for feedback vertex set

DOI10.1145/1721837.1721848zbMath1300.05236OpenAlexW1974810008MaRDI QIDQ2930308

Steéphan Thomassé

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1721837.1721848

zbMATH Keywords

matchingfixed parameter tractabilityfeedback vertex setkernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (91)

Linear kernels for separating a graph into components of bounded size ⋮ Compactors for parameterized counting problems ⋮ On the Complexity of Singly Connected Vertex Deletion ⋮ Safe Approximation and Its Relation to Kernelization ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ Kernelization of Cycle Packing with Relaxed Disjointness Constraints ⋮ A \(13k\)-kernel for planar feedback vertex set via region decomposition ⋮ Kernelization – Preprocessing with a Guarantee ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ On the kernelization of split graph problems ⋮ Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property ⋮ Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ Simultaneous feedback edge set: a parameterized perspective ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ A polynomial kernel for block graph deletion ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments ⋮ Meta-kernelization using well-structured modulators ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Parameterized complexity of vertex deletion into perfect graph classes ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ Circumventing connectivity for kernelization ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Unnamed Item ⋮ Towards optimal kernel for connected vertex cover in planar graphs ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ Kernel bounds for disjoint cycles and disjoint paths ⋮ Contracting graphs to paths and trees ⋮ Lower bounds on kernelization ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Enumerating minimal subset feedback vertex sets ⋮ Kernels for feedback arc set in tournaments ⋮ FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters ⋮ Chordless Cycle Packing Is Fixed-Parameter Tractable ⋮ Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations. ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ Polynomial kernels for deletion to classes of acyclic digraphs ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ On the parameterized complexity of reconfiguration problems ⋮ On parameterized independent feedback vertex set ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion ⋮ Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation) ⋮ Unnamed Item ⋮ Faster deterministic \textsc{Feedback Vertex Set} ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1 ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Dynamic parameterized problems ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ An improved FPT algorithm for independent feedback vertex set ⋮ Sparsity in covering solutions ⋮ On kernels for \(d\)-path vertex cover ⋮ Unnamed Item ⋮ Space-efficient graph kernelizations ⋮ Parameterized complexity of vertex splitting to pathwidth at most 1 ⋮ A polynomial sized kernel for tracking paths problem ⋮ Subset feedback vertex set in chordal and split graphs ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ Parameterized Complexity of Vertex Deletion into Perfect Graph Classes ⋮ Bidimensionality and Kernels ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Unnamed Item ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators ⋮ Euler Digraphs ⋮ On the complexity of singly connected vertex deletion ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size ⋮ Output sensitive fault tolerant maximum matching ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ On sparsification for computing treewidth ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints ⋮ On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments ⋮ On group feedback vertex set parameterized by the size of the cutset

This page was built for publication: A 4 k ² kernel for feedback vertex set