Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

G. Paesani

P. Rzążewski



Contributors

Filippo Bonchi
Editor

Simon J. Puglisi
Editor

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). Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs. In F. Bonchi, & S. J. Puglisi (Eds.), . https://doi.org/10.4230/lipics.mfcs.2021.82

Conference Name MFCS 2021
Conference Location Tallinn, Estonia
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

Files

Accepted Conference Proceeding (932 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright 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





You might also like



Downloadable Citations