Subset Feedback Vertex Set Parameterized by Multiway Cut is FPT
摘要
In the Subset Feedback Vertex Set problem, we are given an undirected graph G, a subset of vertices \(T \subseteq V(G)\) known as terminals, and a positive integer k. The objective is to determine whether there exists a set \(H \subseteq V(G)\) of size at most k such that \(G - H\) does not contain a cycle with a terminal. Subset Feedback Vertex Set generalizes the well-known Feedback Vertex Set problem when \(T {:}{=}V(G)\) ; in the latter problem, the goal is to hit all cycles in the input graph, ensuring that \(G - H\) is acyclic. It was independently shown that Subset Feedback Vertex Set is fixed-parameter tractable when parameterized by the solution size k [Cygan, Pilipczuk, Pilipczuk, and Wojtaszczyk, SIDMA’13; Kawarabayashi, and Kobayashi, JCTB’12]. In this paper, we study Subset Feedback Vertex Set parameterized by a multiway cut \(S \subseteq V(G)\) of the terminal set T, where S is a subset of vertices (potentially containing terminals) such that each connected component of \(G - S\) contains at most one terminal. We show that Subset Feedback Vertex Set parameterized by a multiway cut is fixed-parameter tractable. The use of multiway cut as a parameter was recently studied by Jansen and Swennenhuis [ESA’24] in the context of the Steiner Tree problem.