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.2016.21
URN: urn:nbn:de:0030-drops-69337
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6933/
Go to the corresponding LIPIcs Volume Portal

Majumdar, Diptapriyo

Structural Parameterizations of Feedback Vertex Set

pdf-format:
LIPIcs-IPEC-2016-21.pdf (0.6 MB)

Abstract

A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. It is well-known that the problem of finding a minimum sized (or k sized in case of decision version of) feedback vertex set (FVS) is polynomial time solvable in (sub)-cubic graphs, in pseudo-forests (graphs where each component has at most one cycle) and mock-forests (graph where each vertex is part of at most one cycle). In general graphs, it is known that the problem is NP-Complete, and has an O*((3.619)^k) fixed-parameter algorithm and an O(k^2) kernel where k, the solution size is the parameter. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure of the input. In particular, we show that

* FVS is fixed-parameter tractable, but is unlikely to have polynomial sized kernel when parameterized by the number of vertices of the graph whose degree is at least 4. This answers a question asked in an earlier paper.

* When parameterized by k, the number of vertices, whose deletion results in a pseudo-forest, we give an O(k^6) vertices kernel improving from the previously known O(k^{10}) bound.

* When parameterized by the number k of vertices, whose deletion results in a mock-d-forest, we give a kernel consisting of O(k^{3d+3}) vertices and prove a lower bound of Omega(k^{d+2}) vertices (under complexity theoretic assumptions). Mock-d-forest for a constant d is a mock-forest where each component has at most d cycles.

BibTeX - Entry

@InProceedings{majumdar:LIPIcs:2017:6933,
  author =	{Diptapriyo Majumdar},
  title =	{{Structural Parameterizations of Feedback Vertex Set}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Jiong Guo and Danny Hermelin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6933},
  URN =		{urn:nbn:de:0030-drops-69337},
  doi =		{10.4230/LIPIcs.IPEC.2016.21},
  annote =	{Keywords: Parameterized Complexity, Kernelization, Feedback Vertex Set, Structural Parameterization}
}

Keywords: Parameterized Complexity, Kernelization, Feedback Vertex Set, Structural Parameterization
Collection: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Issue Date: 2017
Date of publication: 09.02.2017

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