Iwata, Yoichi
LinearTime Kernelization for Feedback Vertex Set
Abstract
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 lineartime polynomialsize 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 ksubmodular relaxation, which is a recently developed technique for obtaining efficient FPT algorithms for various problems. The dual of ksubmodular relaxation of Feedback Vertex Set can be seen as a halfintegral variant of Apath packing, and to obtain the lineartime complexity, we give an efficient augmentingpath 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.
BibTeX  Entry
@InProceedings{iwata:LIPIcs:2017:7430,
author = {Yoichi Iwata},
title = {{LinearTime Kernelization for Feedback Vertex Set}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {68:168:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7430},
URN = {urn:nbn:de:0030drops74301},
doi = {10.4230/LIPIcs.ICALP.2017.68},
annote = {Keywords: FPT Algorithms, Kernelization, Path Packing, Halfintegrality}
}
07.07.2017
Keywords: 

FPT Algorithms, Kernelization, Path Packing, Halfintegrality 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 