Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem
- 作者：Ken-ichi Kawarabayashia ; 1 ; k_keniti@nii.ac.jp ; Yusuke Kobayashib ; 2 ; kobayashi@mist.i.u-tokyo.ac.jp
- 关键词：Feedback vertex set ; Cycle packing ; FPT algorithm ; Graph minor
- 刊名：Journal of Combinatorial Theory ; Series B
- 出版年：2012
- 期刊代码：135_00958956
- 类别：cp
- 出版时间：July, 2012
- 卷：102
- 期：4
- 页码：1020-1034
- 文件大小：233 K
摘要
We investigate generalizations of the following well-known problems in the framework of parameterized complexity: the feedback set problem and the cycle packing problem. Our problem setting is that we are given a graph and a vertex set S called 鈥渢erminals鈥? Our purpose here is to consider the following problems:
- abel">1.
The feedback set problem with respect to the terminals S. We call it the subset feedback set problem.
- abel">2.
The cycle packing problem with respect to the terminals S, i.e., each cycle has to contain a vertex in S (such a cycle is called an S-cycle). We call it the S-cycle packing problem.
- abel">1.
For fixed k, we can either find a vertex set X of size k such that has no S-cycle, or conclude that such a vertex set does not exist in time, where n is the number of vertices of the input graph and m is the number of edges of the input graph.
- abel">2.
For fixed k, we can either find k vertex-disjoint S-cycles or conclude that such k disjoint cycles do not exist in time.