2026-07-29T08:41:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11198 2024-03-06T10:47:41Z ddc:004 open_access

An Approximate Kernel for Connected Feedback Vertex Set Ramanujan, M. S. Parameterized Complexity Kernelization Approximation Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik M. S. Ramanujan 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.77 urn:nbn:de:0030-drops-111989 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.77 eng https://creativecommons.org/licenses/by/3.0/legalcode