Feedback Vertex Set (FVS)とは、グラフの頂点の部分集合で、その頂点を取り除いたとき、グラフが閉路をもたなくなるようなもののことです。
最小のFVS, すなわち、最小何頂点取り除いたときにグラフがcycle-freeになるかを求める問題はNP困難な問題として知られています。
この前NIIでwataさんに会ったときにかなり単純なアルゴリズムを教えていただいたのでまとめておきます（調べてもありえないぐらいヒットしなくて困りました）。
問題を判定問題として扱うために、入力はグラフと整数
とし、
が大きさ
以下のFVSをもつか、を判定することにします。
の単純性は仮定しません。
Reduction
の最小次数を3以上にするために以下の操作を繰り返します。
- 頂点
がself-loopをもつ場合、その頂点を削除し、問題の
を1減らす。
- 多重度3以上の辺がある場合、多重度を2にする。
- 次数が1以下の頂点がある場合、削除する。
- 次数2の頂点
すげー命題
最小次数が3以上のグラフについて以下が成り立つ。任意のFVS
について、
の半数より多くの辺が
に含まれる頂点を端点に持つ。
乱択アルゴリズム
上述した命題により、reductionを適用したグラフにおいて、一様ランダムにひとつ辺を選び、さらに一様ランダムにその端点を選ぶ（これは次数に比例してランダムに頂点を選ぶことと等価です）と、その頂点は1/4より大きい確率でFVSに含まれる、ということです。
なので、以下の乱択アルゴリズムを構成することができます。
「reductionを適用したグラフにおいて、閉路がなくなるまで、
での次数に比例した確率で頂点を
個まで順番に選んで削除し、閉路がなくなったらYesを出力する。閉路がなくならなかったらNoを出力する」
このアルゴリズムは、判定問題の答えがYesのとき、少なくともの確率でYesを返します。
参考：
https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (101ページあたり)
う し た ぷ に き あ く ん 笑 （スター稼ぎ用）
