In the Feedback Vertex Set problem, we aim to fnd 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.
Classifying Subset Feedback Vertex Set for H-Free Graphs / Paesani, G; Paulusma, D; Rzazewski, P. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - (2023). [10.1016/j.tcs.2024.114624]
Classifying Subset Feedback Vertex Set for H-Free Graphs
Paesani, G;
2023
Abstract
In the Feedback Vertex Set problem, we aim to fnd 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
