Linear-time Kernelization for Feedback Vertex Set
https://arxiv.org/abs/1608.01463 が ICALP 2017 に採択されたので内容の解説をします．
概略
取り除くと残りが無閉路になる頂点集合を Feedback Vertex Set (FVS)と言い，与えられた無向グラフの最小FVSを求める問題をFVS問題と言います．これは有名なNP困難問題で，FPTアルゴリズムという理論アルゴリズムの研究分野で盛んに研究されており，PACE Challenge*1 というFPTアルゴリズムの実性能を競うコンテストの記念すべき第一回目 (2016年) の題材として選ばれました (ちなみに2017年のコンテストは 5/1 締め切りでまだ間に合うので興味のある方はぜひご参加ください)．この問題に対して，答えが$k$ (頂点数$n$に対してかなり小さいと想定)の時に $4^k n^{O(1)}$ 時間で動作するアルゴリズムを以前開発しており [2] *2，我々の手法の実用性を示すために参加を決めたのがこの研究のキッカケでした．このアルゴリズムは分枝限定法を用いており，実性能も相当高いはずと思っていたのですが，枝刈りに使う下界計算のために指数サイズのLPを解く必要があり（楕円体法で多項式時間にはなる），そのままでは全く速度が出ませんでした．そこで新たに，このLPを爆速で解くアルゴリズムを開発したところ，実はそれを用いて Kernelization という別の研究対象(詳しくは後述)の改善も出来るということに気づき，この論文になりました．ちなみにコンテストの方は @japlj さんと一緒に出てこの論文の手法を実装して優勝しました．
根付きFVSとLP緩和
以下のような根付き版の FVS 問題を考えます．
無向グラフ $G=(V,E)$ と根 $r \in V$ が与えられる．出来るだけ少ない点を除去して，$r$から到達可能な閉路が存在しないようにせよ．
$r$から出発して$r$に戻ってくる$U$-ターンをしない(同じ辺を何度も通っても良いが，辺$uv$の直後に辺$vu$を使うのはダメ) walk 全体を $\mathcal{F}$ としたとき，この問題は以下のような整数計画問題になります．\[\text{minimize} \sum_{v\in V}x(v)\\ \sum_{v\in V(C)} x(v)\geq 1\enspace (\forall C\in \mathcal{F})\\ x(r)=0, x(v)\in\{0,1\}\enspace (\forall v\in V-r)\]
この根付き問題に対するLP緩和の最適解は，$G$のFVSのうちで$r$を含まないようなものの大きさの下界を与えており，以下のような性質を持っています．
- 最適解で $0$, $\frac{1}{2}$, $1$ のみの値を取るものが存在する (Half-integrality)
- 最適半整数解を $x$ とした時，$G$の最小FVSで$r$を含まないものが存在するならば，$r$から$x(v)=0$の点のみを通って到達可能な点集合をどれも含まない最小FVSが存在する．(Persistency)
これらの性質を使うと割と簡単に分枝限定法の探索の深さが $2k$ で抑えられることを示すことが出来，探索木の大きさを $2^{2k}=4^k$ で抑えることが出来ます．
本論文では，このLPを最大流っぽい増大路アルゴリズムで$O(k|E|)$時間で解くアルゴリズムを与え(実装も結構簡単です*3 )，更にこの性質を使うことでグラフの大きさを$k^{O(1)}|E|$時間で$2k^2+k$点，$4k^2$辺まで小さく出来ることを示しています．
FPTアルゴリズムとは
2-SATが充足可能かどうかは線形時間で判定出来る一方で，Max 2-SATはNP困難であり，多項式時間アルゴリズムが存在しないと信じられています．では，「高々 $k$ 個以外の節を充足できるか？」という問題 2-SAT($k$) の計算量はどうなるでしょうか？実は任意の定数 $k$ に対して 2-SAT($k$)は線形時間で解くことが出来ます (具体的には計算量は節の数 $m $ に対して $O(4^k m)$ となる[2])．このように問題にパラメータ $k$ を導入し (Parameterized問題と言う)，$k$の関数 $f(k)$と入力長の多項式時間で解けるとき，その問題は「$k$に関してFPT (Fixed Parameter Tractable)」であると言い，そのようなアルゴリズムをFPTアルゴリズムと呼びます (Max 2-SATは充足されない節の数$k$に関してFPT)．難しい問題(Max 2-SAT)と簡単な特殊ケース(2-SAT)の間を調べる理論という訳です．
普通の多項式時間アルゴリズムの場合，(入力長に対する)多項式が小さなアルゴリズムの方が優れたアルゴリズムです．ではFPTアルゴリズムの場合，$O(4^k n)$ と $O(2^k n^2)$ はどちらが優れているでしょうか？ 当然，どちらが良いかは $k$ と $n$ のバランスに依存します．そのため，通常は入力長の多項式部分は無視して $f(k)$ を出来るだけ小さくする研究と，$f(k)$の部分は無視して入力長の多項式部分を出来るだけ小さく(特に線形に)する研究が並行して行われています．例えば先の 2-SAT($k$) の場合，$f(k)$の部分を小さくする方向の研究では $2.3146^k m^{O(1)}$ が達成されています [4]*4．
Kernelization とは
入力 $x$ とパラメータ $k$ を $(|x|+k)^{O(1)}$ 時間で大きさが高々 $f(k)$ の等価な入力 $x'$ とパラメータ $k'$ に変換する操作 を Kernelization と言います．Kernelize が可能ならば自明に FPT アルゴリズムが得られ (Kernelize 後の入力を自明な全探索で解けば良い)，実はその逆も成立し，FPTであることとKernelize可能であることは等価です．しかし，$k$の多項式にまで入力を小さく出来るかどうかは非自明で，出来るだけ小さなKernel，つまり多項式時間でどこまで入力を圧縮出来るか，が研究されています．
ここでもし，$k^{O(1)}|x|$ 時間で $(x,k)$ を $|x'|\leq k^{O(1)}$ かつ $k'\leq k$ を満たす $(x',k')$ に変形できれば，これを前処理として行ってから$f(k)|x|^{O(1)}$時間のFPTアルゴリズムを適用することで，全体の計算時間は$k^{O(1)}|x|+f(k)|k|^{O(1)}$となります．すなわち，線形時間かつ $f(k)$の部分も($k$の多項式倍を無視して)最小なアルゴリズムが得られるわけです．本論文ではFVS問題に対してこれが可能であると示しています．
*1:https://pacechallenge.wordpress.com/
*2:Yoichi Iwata, Magnus Wahlström, Yuichi Yoshida: Half-integrality, LP-branching, and FPT Algorithms. SIAM J. Comput. 45(4): 1377-1411 (2016)
*3:https://github.com/wata-orz/fvs/blob/master/src/HalfIntegralRelax.java
*4:Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh: Faster Parameterized Algorithms Using Linear Programming. ACM Trans. Algorithms 11(2): 15:1-15:31 (2014)
