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.
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.
| Item Type: | Conference item (Paper) |
|---|---|
| Full text: | (AM) Accepted Manuscript Available under License - Creative Commons Attribution 4.0. Download PDF (911Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://drops.dagstuhl.de/opus/volltexte/2021/14522/ |
| 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
| Export: | |
| Look up in GoogleScholar |
