Agrawal, Akanksha ;
Jain, Pallavi ;
Kanesh, Lawqueen ;
Lokshtanov, Daniel ;
Saurabh, Saket
Conflict Free Feedback Vertex Set: A Parameterized Dichotomy
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 FCFFeedback Vertex Set (FCFFVS, for short). The FCFFVS 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 GS 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, FCFFVS is W[1]hard on general graphs and admits an FPT algorithm if F is the family of ddegenerate graphs. In this paper, we relate FCFFVS to the Independent Set problem on special classes of graphs, and obtain a complete dichotomy result on the Parameterized Complexity of the problem FCFFVS, when F is a hereditary graph family. In particular, we show that FCFFVS 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 FCFFVS. 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, BCFFVS 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)^(2epsilon), and show that F_epsilonCFFVS 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:153:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9635},
URN = {urn:nbn:de:0030drops96355},
doi = {10.4230/LIPIcs.MFCS.2018.53},
annote = {Keywords: Conflictfree, Feedback Vertex Set, FPT algorithm, W[1]hardness}
}
27.08.2018
Keywords: 

Conflictfree, 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: 

27.08.2018 