2026-07-20T05:31:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8230 2024-03-06T10:41:47Z ddc:004 open_access

Independent Feedback Vertex Set for P_5-free Graphs Bonamy, Marthe Dabrowski, Konrad K. Feghali, Carl Johnson, Matthew Paulusma, Daniël feedback vertex set odd cycle transversal independent set H-free graph The NP-complete problem Feedback Vertex Set is to decide if it is possible, for a given integer k>=0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding if a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P_4-free graphs. We show that it remains in P for P_5-free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks if a graph has an independent odd cycle transversal of size at most k for a given integer k>=0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marthe Bonamy and Konrad K. Dabrowski and Carl Feghali and Matthew Johnson and Daniël Paulusma 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.16 urn:nbn:de:0030-drops-82308 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.16 eng https://creativecommons.org/licenses/by/3.0/legalcode