We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Computing weighted subset transversals in H-free graphs

Brettell, N. and Johnson, M. and Paulusma, D. (2021) 'Computing weighted subset transversals in H-free graphs.', WADS 2021 Halifax, Nova Scotia, 9-11 Aug 2021.


For the Odd Cycle Transversal problem, the task is to nd a small set S of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal 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. Our general approach can also be used for Weighted Subset Feedback Vertex Set, which enables us to generalize a recent result of Papadopoulos and Tzimas.

Item Type:Conference item (Paper)
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Publisher Web site:
Date accepted:13 April 2021
Date deposited:01 June 2021
Date of first online publication:2021
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar