On the approximate compressibility of connected vertex cover
From MaRDI portal
Publication:2006945
Abstract: The Connected Vertex Cover problem, where the goal is to compute a minimum set of vertices in a given graph which forms a vertex cover and induces a connected subgraph, is a fundamental combinatorial problem and has received extensive attention in various subdomains of algorithmics. In the area of kernelization, it is known that this problem is unlikely to have efficient preprocessing algorithms, also known as polynomial kernelizations. However, it has been shown in a recent work of Lokshtanov et al. [STOC 2017] that if one considered an appropriate notion of approximate kernelization, then this problem parameterized by the solution size does admit an approximate polynomial kernelization. In fact, Lokhtanov et al. were able to obtain a polynomial size approximate kernelization scheme (PSAKS) for Connected Vertex Cover parameterized by the solution size. A PSAKS is essentially a preprocessing algorithm whose error can be made arbitrarily close to 0. In this paper we revisit this problem, and consider parameters that are strictly smaller than the size of the solution and obtain the first polynomial size approximate kernelization schemes for the Connected Vertex Cover problem when parameterized by the deletion distance of the input graph to the class of cographs, the class of bounded treewidth graphs, and the class of all chordal graphs.
Recommendations
- Revisiting connected vertex cover: FPT algorithms and lossy kernels
- Lossy kernelization
- Towards optimal kernel for connected vertex cover in planar graphs
- Complexity and Approximation Results for the Connected Vertex Cover Problem
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
Cites work
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- A completeness theory for polynomial (Turing) kernelization
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- Algorithmic graph theory and perfect graphs
- Approximation and kernelization for chordal vertex deletion
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Depth-first search and the vertex cover problem
- Graph operations characterizing rank-width
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Infeasibility of instance compression and succinct PCPs for NP
- Kernelization -- preprocessing with a guarantee
- Kernelization Lower Bounds by Cross-Composition
- Kernelization lower bounds through colors and IDs
- Kernelization of packing problems
- Kernelization. Theory of parameterized preprocessing
- Lossy kernelization
- New limits to classical and quantum instance compression
- On problems without polynomial kernels
- On the Relationship Between Clique-Width and Treewidth
- On the hardness of losing width
- Parameterized algorithms
- Parametrized complexity theory.
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Rank-width and vertex-minors
- Recent developments in kernelization: a survey
- Representative sets and irrelevant vertices: new tools for kernelization
- Revisiting connected vertex cover: FPT algorithms and lossy kernels
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Smaller parameters for vertex cover kernelization
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Vertex cover structural parameterization revisited
Cited in
(5)
This page was built for publication: On the approximate compressibility of connected vertex cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2006945)
