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 (911Kb)
|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
|Look up in GoogleScholar|