2026-07-20T05:05:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9635 2024-03-06T10:44:35Z ddc:004 open_access

Conflict Free Feedback Vertex Set: A Parameterized Dichotomy Agrawal, Akanksha Jain, Pallavi Kanesh, Lawqueen Lokshtanov, Daniel Saurabh, Saket Conflict-free Feedback Vertex Set FPT algorithm W[1]-hardness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Akanksha Agrawal and Pallavi Jain and Lawqueen Kanesh and Daniel Lokshtanov and Saket Saurabh 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.53 urn:nbn:de:0030-drops-96355 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.53 eng https://creativecommons.org/licenses/by/3.0/legalcode