We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs

Paesani, G. and Paulusma, D. and Rzążewski, P. (2021) 'Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs.', MFCS 2021 Tallinn, Estonia, 23-27 Aug 2021.


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.

Item Type:Conference item (Paper)
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution 4.0.
Download PDF
Publisher Web site:
Publisher statement:© Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski; licensed under Creative Commons License CC-BY 4.0 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Editors: Filippo Bonchi and Simon J. Puglisi; Article No. 82; pp. 82:1–82:14 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
Date accepted:29 June 2021
Date deposited:24 August 2021
Date of first online publication:18 August 2021
Date first made open access:24 August 2021

Save or Share this output

Look up in GoogleScholar