On the Approximate Compressibility of Connected Vertex Cover
- PDF / 2,837,824 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 84 Downloads / 212 Views
On the Approximate Compressibility of Connected Vertex Cover Diptapriyo Majumdar1 · M. S. Ramanujan2 · Saket Saurabh3 Received: 16 April 2019 / Accepted: 28 March 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 a polynomial kernelization algorithm. However, it has been shown in a recent work of Lokshtanov et al. (Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC 2017, Montreal, QC, Canada, 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, Lokshtanov 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. Keywords Parameterized complexity · Kernelization · Connected vertex cover · Approximate kernelization
A part of this work was done when the first author was affiliated to The Institute of Mathematical Sciences, HBNI, Chennai, India. * Diptapriyo Majumdar [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
1 Introduction Polynomial-time preprocessing is one of the widely used methods to tackle NPhardness in practice, and kernelization has been extremely successful in laying down a mathematical framework for the design and rigorous analysis of preprocessing algorithms for decision problems. The central notion in kernelization is that of a kernelization, which is a preprocessing algorithm that takes as input a parameterized problem, which is a pair (I, k), where I is the problem instance and k is an integer called the parameter. A kernelization is required to run in polynomial-time and convert a potentially large input (I, k) into an equivalent instance (I � , k� ) such that |I ′ | and k′ are both bounded by a function of the parameter k. Over the last decade, the area of kernelization has seen the development of a wide range of tools to design preprocessing algorithms and a rich theory of lower bounds has been developed based on assumptions from complexity theory [1, 2, 10–12, 14, 17, 19,
Data Loading...
