On the approximate compressibility of connected vertex cover
From MaRDI portal
Publication:2006945
DOI10.1007/S00453-020-00708-4zbMATH Open1455.68144arXiv1905.03379OpenAlexW2944564962MaRDI QIDQ2006945FDOQ2006945
Authors: Diptapriyo Majumdar, M. S. Ramanujan, Saket Saurabh 
Publication date: 12 October 2020
Published in: Algorithmica (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1905.03379
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
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- On problems without polynomial kernels
- Depth-first search and the vertex cover problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Algorithmic graph theory and perfect graphs
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Kernelization -- preprocessing with a guarantee
- Recent developments in kernelization: a survey
- Representative sets and irrelevant vertices: new tools for kernelization
- On the Relationship Between Clique-Width and Treewidth
- Parameterized algorithms
- Title not available (Why is that?)
- Kernelization lower bounds through colors and IDs
- Kernelization Lower Bounds by Cross-Composition
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Infeasibility of instance compression and succinct PCPs for NP
- Rank-width and vertex-minors
- New limits to classical and quantum instance compression
- Kernelization of packing problems
- Title not available (Why is that?)
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- On the hardness of losing width
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Smaller parameters for vertex cover kernelization
- Graph operations characterizing rank-width
- Vertex cover structural parameterization revisited
- A completeness theory for polynomial (Turing) kernelization
- Approximation and kernelization for chordal vertex deletion
- Kernelization. Theory of parameterized preprocessing
- Lossy kernelization
- Revisiting connected vertex cover: FPT algorithms and lossy kernels
- Polynomial kernels for vertex cover parameterized by small degree modulators
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
Cited In (4)
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)
