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

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

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

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

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

Reduction

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

  1. 頂点 vがself-loopをもつ場合、その頂点を削除し、問題の kを1減らす。
  2. 多重度3以上の辺がある場合、多重度を2にする。
  3. 次数が1以下の頂点がある場合、削除する。
  4. 次数2の頂点 vがある場合、 vを削除し、 vにつながっていた2頂点を新たに辺で結ぶ。
  5.  kが負なら"No"を返してアルゴリズムを終了する。

すげー命題

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

乱択アルゴリズム

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

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

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

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

参考:

https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (101ページあたり)

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