Skip to main content

Research Repository

Advanced Search

Computing subset transversals in H-free graphs

Brettell, N.; Johnson, M.; Paesani, G.; Paulusma, D.

Computing subset transversals in H-free graphs Thumbnail


Authors

N. Brettell

G. Paesani



Abstract

we study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to H-free graphs, that is, to graphs that do not contain some fixed graph H as an induced subgraph. By combining known and new results, we determine the computational complexity of both problems on H-free graphs for every graph H except when H = sP1 + P4 for some s ≥ 1. As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomial-time solvable for (sP1 + P4)-free graphs for every s ≥ 1

Citation

Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2022). Computing subset transversals in H-free graphs. Theoretical Computer Science, 902, 76-92. https://doi.org/10.1016/j.tcs.2021.12.010

Journal Article Type Article
Acceptance Date Dec 17, 2021
Online Publication Date Dec 21, 2021
Publication Date Jan 18, 2022
Deposit Date Dec 31, 2021
Publicly Available Date Dec 21, 2022
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 902
Pages 76-92
DOI https://doi.org/10.1016/j.tcs.2021.12.010
Public URL https://durham-repository.worktribe.com/output/1221498

Files





You might also like



Downloadable Citations