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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Subset Feedback Vertex Set Parameterized by Multiway Cut is FPT

  • Sriram Bhyravarapu,
  • Shashanka Kulamarva,
  • Pritesh Kumar,
  • Shivesh K. Roy,
  • Saket Saurabh

摘要

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.