2026-07-22T01:29:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7430 2024-03-06T10:40:24Z ddc:004 open_access

Linear-Time Kernelization for Feedback Vertex Set Iwata, Yoichi FPT Algorithms Kernelization Path Packing Half-integrality In this paper, we give an algorithm that, given an undirected graph G of m edges and an integer k, computes a graph G' and an integer k' in O(k^4 m) time such that (1) the size of the graph G' is O(k^2), (2) k' \leq k, and (3) G has a feedback vertex set of size at most k if and only if G' has a feedback vertex set of size at most k'. This is the first linear-time polynomial-size kernel for Feedback Vertex Set. The size of our kernel is 2k^2+k vertices and 4k^2 edges, which is smaller than the previous best of 4k^2 vertices and 8k^2 edges. Thus, we improve the size and the running time simultaneously. We note that under the assumption of NP \not\subseteq coNP/poly, Feedback Vertex Set does not admit an O(k^{2-\epsilon})-size kernel for any \epsilon>0. Our kernel exploits k-submodular relaxation, which is a recently developed technique for obtaining efficient FPT algorithms for various problems. The dual of k-submodular relaxation of Feedback Vertex Set can be seen as a half-integral variant of A-path packing, and to obtain the linear-time complexity, we give an efficient augmenting-path algorithm for this problem. We believe that this combinatorial algorithm is of independent interest. A solver based on the proposed method won first place in the 1st Parameterized Algorithms and Computational Experiments (PACE) challenge. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yoichi Iwata 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.68 urn:nbn:de:0030-drops-74301 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.68 eng https://creativecommons.org/licenses/by/3.0/legalcode