An approximate kernel for connected feedback vertex set

DOI10.4230/LIPICS.ESA.2019.77MaRDI QIDQ5075825zbMATH OpenFDO

Authors

Publication date 11 May 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2019.77

zbMATH Keywords

approximation algorithmskernelizationparameterized complexity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• On the approximate compressibility of connected vertex cover
• A Cubic Kernel for Feedback Vertex Set
• Connected feedback vertex set on AT-free graphs
• A quadratic kernel for feedback vertex set
• Kernelization for feedback vertex set via elimination distance to a forest

Cites work

• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A 4k^2 kernel for feedback vertex set
• A completeness theory for polynomial (Turing) kernelization
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Connected feedback vertex set in planar graphs
• Cross-composition: a new technique for kernelization lower bounds
• FPT algorithms for connected feedback vertex set
• scientific article; zbMATH DE number 7053262 (Why is no real title available?)
• Infeasibility of instance compression and succinct PCPs for NP
• Kernelization -- preprocessing with a guarantee
• Kernelization lower bounds through colors and IDs
• Kernelization of packing problems
• Lossy kernelization
• Lossy kernels for connected dominating set on sparse graphs
• Lossy Kernels for Hitting Subgraphs
• New limits to classical and quantum instance compression
• On problems without polynomial kernels
• Parameterized algorithms
• Recent developments in kernelization: a survey
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems

Cited in

(8)

• A randomized polynomial kernel for subset feedback vertex set
• \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
• Circumventing connectivity for kernelization
• Approximate Turing Kernelization for Problems Parameterized by Treewidth
• On the lossy kernelization for connected treedepth deletion set
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• Connected feedback vertex set on AT-free graphs
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion

This page was built for publication: An approximate kernel for connected feedback vertex set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075825)