2026-07-22T00:07:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14522 2024-03-06T10:54:13Z ddc:004 open_access

Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs Paesani, Giacomo Paulusma, Daniël Rzążewski, Paweł Feedback vertex set even cycle transversal odd cactus forest block We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that both problems are polynomial-time solvable for sP₃-free graphs for every integer s ≥ 1; here, the graph sP₃ denotes the disjoint union of s paths on three vertices. Our results show that both problems exhibit the same behaviour on H-free graphs (subject to some open cases). This is in part explained by a new general algorithm we design for finding in a graph G a largest induced subgraph whose blocks belong to some finite class C of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on H-free graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giacomo Paesani and Daniël Paulusma and Paweł Rzążewski 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.82 urn:nbn:de:0030-drops-145224 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.82 eng https://creativecommons.org/licenses/by/4.0/legalcode