Minimum Feedback Vertex Setの乱択アルゴリズム

Feedback Vertex Set (FVS)とは、グラフ $G$ の頂点の部分集合で、その頂点を取り除いたとき、グラフが閉路をもたなくなるようなもののことです。

最小のFVS, すなわち、最小何頂点取り除いたときにグラフがcycle-freeになるかを求める問題はNP困難な問題として知られています。

この前NIIでwataさんに会ったときにかなり単純なアルゴリズムを教えていただいたのでまとめておきます（調べてもありえないぐらいヒットしなくて困りました）。

問題を判定問題として扱うために、入力はグラフ $G$ と整数 $k$ とし、 $G$ が大きさ $k$ 以下のFVSをもつか、を判定することにします。 $G$ の単純性は仮定しません。

$G$ の最小次数を3以上にするために以下の操作を繰り返します。

最小次数が3以上のグラフ $G$ について以下が成り立つ。任意のFVS $X$ について、 $G$ の半数より多くの辺が $X$ に含まれる頂点を端点に持つ。

上述した命題により、reductionを適用したグラフにおいて、一様ランダムにひとつ辺を選び、さらに一様ランダムにその端点を選ぶ（これは次数に比例してランダムに頂点を選ぶことと等価です）と、その頂点は1/4より大きい確率でFVSに含まれる、ということです。

なので、以下の乱択アルゴリズムを構成することができます。

「reductionを適用したグラフ $G$ において、閉路がなくなるまで、 $G$ での次数に比例した確率で頂点を $k$ 個まで順番に選んで削除し、閉路がなくなったらYesを出力する。閉路がなくならなかったらNoを出力する」

このアルゴリズムは、判定問題の答えがYesのとき、少なくとも $4^{-k}$ の確率でYesを返します。

参考：

う　し　た　ぷ　に　き　あ　く　ん　笑　（スター稼ぎ用）

Joeの精進記録