- 著者
- 田村 祐馬 伊藤 健洋 周 暁
- 雑誌
- 研究報告アルゴリズム(AL)
- 巻号頁・発行日
- vol.2014-AL-148, no.3, pp.1-6, 2014-06-06
無向グラフ G のフィードバック点集合 F とは,G から F を取り除くと,残されたグラフが林になるような G の点部分集合のことである.また,F が G の独立点集合をなすとき,F はフィードバック独立点集合という.本稿では,与えられたグラフに対し,点数が最小のフィードバック独立点集合を求める問題について研究する.この問題は,平面的二部グラフに対してさえ NP 困難であることが示せるため,我々はいくつかの特別なグラフクラスに着目する.まず我々は,この問題が木幅制限グラフと弦グラフに対して線形時間で解けることを示す.次に,平面グラフに対しては,解のサイズをパラメータとした FPT アルゴリズムを与える.