Brettell, N. and Johnson, M. and Paulusma, D. (2022) 'Computing Weighted Subset Odd Cycle Transversals in H-free graphs.', Journal of computer and system sciences., 128 . pp. 71-85.
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.
|Full text:||Publisher-imposed embargo until 08 April 2023. |
(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
File format - PDF (532Kb)
|Publisher Web site:||https://doi.org/10.1016/j.jcss.2022.03.002|
|Publisher statement:||© 2022. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/|
|Date accepted:||21 March 2022|
|Date deposited:||19 May 2022|
|Date of first online publication:||08 April 2022|
|Date first made open access:||08 April 2023|
Save or Share this output
|Look up in GoogleScholar|