Skip to main content

Research Repository

Advanced Search

Computing weighted subset odd cycle transversals in H-free graphs

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

Computing weighted subset odd cycle transversals in H-free graphs Thumbnail


Authors

N. Brettell



Abstract

For the Odd Cycle Transversal problem, the task is to find a small set S of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal problem requires S to intersect only those odd cycles that include a vertex of a distinguished vertex subset T. If we are given weights for the vertices, we ask instead that S has small weight: this is the problem Weighted Subset Odd Cycle Transversal. We prove an almost-complete complexity dichotomy for Weighted Subset Odd Cycle Transversal for graphs that do not contain a graph H as an induced subgraph. In particular, our result shows that the complexities of the weighted and unweighted variant do not align on H-free graphs, just as Papadopoulos and Tzimas showed for Subset Feedback Vertex Set.

Citation

Brettell, N., Johnson, M., & Paulusma, D. (2022). Computing weighted subset odd cycle transversals in H-free graphs. Journal of Computer and System Sciences, 128, 71-85. https://doi.org/10.1016/j.jcss.2022.03.002

Journal Article Type Article
Acceptance Date Mar 21, 2022
Online Publication Date Apr 8, 2022
Publication Date 2022-09
Deposit Date May 18, 2022
Publicly Available Date Apr 8, 2023
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 128
Pages 71-85
DOI https://doi.org/10.1016/j.jcss.2022.03.002
Public URL https://durham-repository.worktribe.com/output/1207719

Files





You might also like



Downloadable Citations