Bonnet, Édouard ;
Brettell, Nick ;
Kwon, Ojoung ;
Marx, Dániel
Generalized Feedback Vertex Set Problems on BoundedTreewidth Graphs: Chordality Is the Key to SingleExponential Parameterized Algorithms
Abstract
It has long been known that Feedback Vertex Set can be solved in time 2^O(w log w)n^O(1) on graphs of treewidth w, but it was only recently that this running time was improved to 2^O(w)n^O(1), that is, to singleexponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class of graphs P, Bounded PBlock Vertex Deletion asks, given a graph G on n vertices and positive integers k and d, whether G contains a set S of at most k vertices
such that each block of GS has at most d vertices and is in P. Assuming that P is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when singleexponential parameterized algorithms are possible for fixed values of d:
 if P consists only of chordal graphs, then the problem can be solved in time 2^O(wd^2) n^{O}(1),
 if P contains a graph with an induced cycle of length ell>= 4, then the problem is not solvable in time 2^{o(w log w)} n^O(1)} even for fixed d=ell, unless the ETH fails.
We also study a similar problem, called Bounded PComponent Vertex Deletion, where the target graphs have connected components of small size instead of having blocks of small size, and present analogous results.
BibTeX  Entry
@InProceedings{bonnet_et_al:LIPIcs:2018:8565,
author = {{\'E}douard Bonnet and Nick Brettell and Ojoung Kwon and D{\'a}niel Marx},
title = {{Generalized Feedback Vertex Set Problems on BoundedTreewidth Graphs: Chordality Is the Key to SingleExponential Parameterized Algorithms}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {7:17:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770514},
ISSN = {18688969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8565},
URN = {urn:nbn:de:0030drops85653},
doi = {10.4230/LIPIcs.IPEC.2017.7},
annote = {Keywords: fixedparameter tractable algorithms, treewidth, feedback vertex set}
}
02.03.2018
Keywords: 

fixedparameter tractable algorithms, treewidth, feedback vertex set 
Seminar: 

12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Issue date: 

2018 
Date of publication: 

02.03.2018 