G. Paesani
Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs
Paesani, G.; Paulusma, D.; Rzążewski, P.
Authors
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
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 |
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
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2018)
Presentation / Conference Contribution
Computing subset transversals in H-free graphs
(2021)
Journal Article
Bounding the mim-width of hereditary graph classes
(2021)
Journal Article
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
(2021)
Journal Article
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
(2020)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search