Classifying Subset Feedback Vertex Set for H-free graphs

Paesani, G.; Paulusma, D.; Rzążewski, P.

Abstract

In the FEEDBACK VERTEX SET problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The SUBSET FEEDBACK VERTEX SET problem requires S to intersect only those cycles that include a vertex of some specified set T. We also consider the WEIGHTED SUBSET FEEDBACK VERTEX SET problem, where each vertex u has weight w(u)>0 and we ask that S has small weight. By combining known NP-hardness results with new polynomial-time results we prove full complexity dichotomies for SUBSET FEEDBACK VERTEX SET and WEIGHTED SUBSET FEEDBACK VERTEX SET for H-free graphs, that is, graphs that do not contain a graph H as an induced subgraph.

Citation

Paesani, G., Paulusma, D., & Rzążewski, P. (2022). Classifying Subset Feedback Vertex Set for H-free graphs. In M. A. Bekos, & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science. WG 2022 (412-424). https://doi.org/10.1007/978-3-031-15914-5_30

• Conference Name: WG 2022
• Acceptance Date: Jul 15, 2022
• Online Publication Date: Oct 1, 2022
• Publication Date: 2022
• Deposit Date: Oct 16, 2022
• Publicly Available Date: Oct 17, 2022
• Volume: 13453
• Pages: 412-424
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-Theoretic Concepts in Computer Science. WG 2022.
• ISBN: 978-3-031-15913-8
• DOI: https://doi.org/10.1007/978-3-031-15914-5_30
• Public URL: https://durham-repository.worktribe.com/output/1134856