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



Contributors

I. Adler
Editor

H. Müller
Editor

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. (2020). Computing subset transversals in H-free graphs. In I. Adler, & H. Müller (Eds.), WG 2020: Graph-Theoretic Concepts in Computer Science (187-199). https://doi.org/10.1007/978-3-030-60440-0_15

Conference Name WG 2020
Conference Location Leeds, England
Acceptance Date Apr 27, 2020
Online Publication Date Oct 9, 2020
Publication Date Oct 9, 2020
Deposit Date Jul 12, 2020
Publicly Available Date Jan 21, 2021
Volume 12301
Pages 187-199
Series Title Lecture Notes in Computer Science
Series ISSN 0302-9743,1611-3349
Book Title WG 2020: Graph-Theoretic Concepts in Computer Science
ISBN 9783030604394
DOI https://doi.org/10.1007/978-3-030-60440-0_15
Public URL https://durham-repository.worktribe.com/output/1140880

Files





You might also like



Downloadable Citations