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

Paesani, G.; Paulusma, D.; Rzążewski, P.

Abstract

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.

Citation

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

• Presentation Conference Type: Conference Paper (published)
• Conference Name: MFCS 2021
• Start Date: Aug 23, 2021
• End Date: Aug 27, 2021
• Acceptance Date: Jun 29, 2021
• Online Publication Date: Aug 18, 2021
• Publication Date: 2021
• Deposit Date: Aug 23, 2021
• Publicly Available Date: Aug 24, 2021
• Volume: 202
• Pages: 1-14
• Series Title: Leibniz International Proceedings in Informatics
• DOI: https://doi.org/10.4230/lipics.mfcs.2021.82
• Public URL: https://durham-repository.worktribe.com/output/1139079