Skip to main content

Research Repository

Advanced Search

Computing weighted subset transversals in H-free graphs

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

Computing weighted subset transversals in H-free graphs Thumbnail


Authors

N. Brettell



Contributors

A. Lubiw
Editor

M. Salavatipour
Editor

Abstract

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.

Citation

Brettell, N., Johnson, M., & Paulusma, D. (2021). Computing weighted subset transversals in H-free graphs. In A. Lubiw, M. Salavatipour, & M. He (Eds.), Algorithms and Data Structures 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (229-242). https://doi.org/10.1007/978-3-030-83508-8_17

Conference Name WADS 2021
Conference Location Halifax, Nova Scotia
Start Date Aug 9, 2021
End Date Aug 11, 2021
Acceptance Date Apr 13, 2021
Online Publication Date Jul 31, 2021
Publication Date 2021
Deposit Date May 28, 2021
Publicly Available Date Mar 28, 2024
Publisher Springer Verlag
Pages 229-242
Series Title Lecture Notes in Computer Science
Series Number 12808
Series ISSN 0302-9743
Book Title Algorithms and Data Structures 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings
ISBN 978-3-030-83507-1
DOI https://doi.org/10.1007/978-3-030-83508-8_17
Public URL https://durham-repository.worktribe.com/output/1139387

Files





You might also like



Downloadable Citations