License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.53
URN: urn:nbn:de:0030-drops-96355
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9635/
Go to the corresponding LIPIcs Volume Portal


Agrawal, Akanksha ; Jain, Pallavi ; Kanesh, Lawqueen ; Lokshtanov, Daniel ; Saurabh, Saket

Conflict Free Feedback Vertex Set: A Parameterized Dichotomy

pdf-format:
LIPIcs-MFCS-2018-53.pdf (0.6 MB)


Abstract

In this paper we study recently introduced conflict version of the classical Feedback Vertex Set (FVS) problem. For a family of graphs F, we consider the problem F-CF-Feedback Vertex Set (F-CF-FVS, for short). The F-CF-FVS problem takes as an input a graph G, a graph H in F (where V(G)=V(H)), and an integer k, and the objective is to decide if there is a set S subseteq V(G) of size at most k such that G-S is a forest and S is an independent set in H. Observe that if we instantiate F to be the family of edgeless graphs then we get the classical FVS problem. Jain, Kanesh, and Misra [CSR 2018] showed that in contrast to FVS, F-CF-FVS is W[1]-hard on general graphs and admits an FPT algorithm if F is the family of d-degenerate graphs. In this paper, we relate F-CF-FVS to the Independent Set problem on special classes of graphs, and obtain a complete dichotomy result on the Parameterized Complexity of the problem F-CF-FVS, when F is a hereditary graph family. In particular, we show that F-CF-FVS is FPT parameterized by the solution size if and only if F+Cluster IS is FPT parameterized by the solution size. Here, F+Cluster IS is the Independent Set problem in the (edge) union of a graph G in F and a cluster graph H (G and H are explicitly given). Next, we exploit this characterization to obtain new FPT results as well as intractability results for F-CF-FVS. In particular, we give an FPT algorithm for F+Cluster IS when F is the family of K_{i,j}-free graphs. We show that for the family of bipartite graph B, B-CF-FVS is W[1]-hard, when parameterized by the solution size. Finally, we consider, for each 0< epsilon<1, the family of graphs F_epsilon, which comprise of graphs G such that |E(G)| <= |V(G)|^(2-epsilon), and show that F_epsilon-CF-FVS is W[1]-hard, when parameterized by the solution size, for every 0<epsilon<1.

BibTeX - Entry

@InProceedings{agrawal_et_al:LIPIcs:2018:9635,
  author =	{Akanksha Agrawal and Pallavi Jain and Lawqueen Kanesh and Daniel Lokshtanov and Saket Saurabh},
  title =	{{Conflict Free Feedback Vertex Set: A Parameterized Dichotomy}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{53:1--53:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9635},
  URN =		{urn:nbn:de:0030-drops-96355},
  doi =		{10.4230/LIPIcs.MFCS.2018.53},
  annote =	{Keywords: Conflict-free, Feedback Vertex Set, FPT algorithm, W[1]-hardness}
}

Keywords: Conflict-free, Feedback Vertex Set, FPT algorithm, W[1]-hardness
Seminar: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 20.08.2018


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