@techreport{oai:ipsj.ixsq.nii.ac.jp:00101690,
 author = {田村, 祐馬 and 伊藤, 健洋 and 周, 暁 and Yuma, Tamura and Takehiro, Ito and Xiao, Zhou},
 issue = {3},
 month = {Jun},
 note = {無向グラフ G のフィードバック点集合 Ｆ とは，G から F を取り除くと，残されたグラフが林になるような G の点部分集合のことである．また，Ｆ が G の独立点集合をなすとき，Ｆ はフィードバック独立点集合という．本稿では，与えられたグラフに対し，点数が最小のフィードバック独立点集合を求める問題について研究する．この問題は，平面的二部グラフに対してさえ NP 困難であることが示せるため，我々はいくつかの特別なグラフクラスに着目する．まず我々は，この問題が木幅制限グラフと弦グラフに対して線形時間で解けることを示す．次に，平面グラフに対しては，解のサイズをパラメータとした FPT アルゴリズムを与える．, A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices. This problem is NP-hard even for planar bipartite graphs, and hence we focus on some special classes of graphs. We first show that the problem is solvable in linear time for bounded treewidth graphs and chordal graphs. Then, we give an FPT algorithm for planar graphs when parameterized by the solution size.},
 title = {フィードバック独立点集合問題},
 year = {2014}
}