License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.77
URN: urn:nbn:de:0030-drops-111989
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11198/
Ramanujan, M. S.
An Approximate Kernel for Connected Feedback Vertex Set
Abstract
The Feedback Vertex Set problem is a fundamental computational problem which has been the subject of intensive study in various domains of algorithmics. In this problem, one is given an undirected graph G and an integer k as input. The objective is to determine whether at most k vertices can be deleted from G such that the resulting graph is acyclic. The study of preprocessing algorithms for this problem has a long and rich history, culminating in the quadratic kernelization of Thomasse [SODA 2010].
However, it is known that when the solution is required to induce a connected subgraph (such a set is called a connected feedback vertex set), a polynomial kernelization is unlikely to exist and the problem is NP-hard to approximate below a factor of 2 (assuming the Unique Games Conjecture).
In this paper, we show that if one is interested in only preserving approximate solutions (even of quality arbitrarily close to the optimum), then there is a drastic improvement in our ability to preprocess this problem. Specifically, we prove that for every fixed 0<epsilon<1, graph G, and k in N, the following holds:
There is a polynomial time computable graph G' of size k^O(1) such that for every c >= 1, any c-approximate connected feedback vertex set of G' of size at most k is a c * (1+epsilon)-approximate connected feedback vertex set of G.
Our result adds to the set of approximate kernelization algorithms introduced by Lokshtanov et al. [STOC 2017]. As a consequence of our main result, we show that Connected Feedback Vertex Set can be approximated within a factor min{OPT^O(1),n^(1-delta)} in polynomial time for some delta>0.
BibTeX - Entry
@InProceedings{ramanujan:LIPIcs:2019:11198,
author = {M. S. Ramanujan},
title = {{An Approximate Kernel for Connected Feedback Vertex Set}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {77:1--77:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11198},
URN = {urn:nbn:de:0030-drops-111989},
doi = {10.4230/LIPIcs.ESA.2019.77},
annote = {Keywords: Parameterized Complexity, Kernelization, Approximation Algorithms}
}
|
Keywords: |
|
Parameterized Complexity, Kernelization, Approximation Algorithms |
|
Collection: |
|
27th Annual European Symposium on Algorithms (ESA 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.09.2019 |
