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.IPEC.2017.7
URN: urn:nbn:de:0030-drops-85653
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8565/
Go to the corresponding LIPIcs Volume Portal

Bonnet, Édouard ; Brettell, Nick ; Kwon, O-joung ; Marx, Dániel

Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms

pdf-format:
LIPIcs-IPEC-2017-7.pdf (0.6 MB)

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 single-exponential 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 P-Block 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 G-S 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 single-exponential 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 P-Component 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 O-joung Kwon and D{\'a}niel Marx},
  title =	{{Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8565},
  URN =		{urn:nbn:de:0030-drops-85653},
  doi =		{10.4230/LIPIcs.IPEC.2017.7},
  annote =	{Keywords: fixed-parameter tractable algorithms, treewidth, feedback vertex set}
}

Keywords: fixed-parameter tractable algorithms, treewidth, feedback vertex set
Collection: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Issue Date: 2018
Date of publication: 02.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI