0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time FPT Algorithms
NIIの吉田さん、阪大の山口さんとの共著論文 https://arxiv.org/abs/1704.02700 が理論計算機科学のトップ会議FOCS 2018に採択されました。
概略
与えられたグラフが森か？二部か？与えられた2-CNFが充足可能か？など様々な問題が単純なDFS (unit propagation)によって線形時間で判定可能です。一方で、Noの場合に出来るだけ少ない個数の頂点(or 辺)・変数(or 制約)などを除去してYesにする最適化問題は多くの場合にNP困難となります。最適値を$k$とすると、$k=0$は超簡単（線形時間）ですが、$k$が一般の場合は激ムズ（NP困難）というわけです。では、$k$が小さい定数の場合はどうでしょうか？本研究では、このようなunit-propagationにより線形時間で解けるタイプの問題に対し、任意の定数$k$に対して線形時間で動作するアルゴリズムを与えました。問題ごとに専用のアルゴリズムを作って各個撃破するのではなく、分枝限定法＋増大路という一つの枠組みで様々な問題に適用できます。アルゴリズムは結構複雑ですが、実性能も結構高いだろうと思っています。せっかくなので今回の手法を用いると解ける競プロの例題を一つ作ってみました。
例題
$n (\leq 10^5)$人の間で$m (\leq 10^5)$回背比べをしました。$i$回目は$a_i$君と$b_i$君が背比べをし、$a_i$君の身長より$b_i$君の身長がちょうど$c_i (\leq 10^9)$cmだけ高かったそうです。$n$人のうち何人かはズルをして背伸びをしたりしゃがんだりして身長をごまかしため、結果に矛盾が生じているようです。少なくとも何人がズルをしたか計算して下さい。6人以上がズルをした場合は"Too many"と出力して下さい。
サンプル入力: n=4, (a,b,c)=[(1, 2, 1), (1, 3, 2), (1, 4, 3), (2, 3, 1), (2, 4, 1), (3, 4, 2)]
サンプル出力: 1 (4番がズルをして、残りの身長が(例えば)それぞれ1cm, 2cm, 3cm)
背景
パラメータ$k$に対して$f(k)\mathrm{poly}(n)$という形の計算時間で動作するアルゴリズムはFPT (Fixed Parameter Tractable)と呼ばれます。上の例のように、$k=0$だと簡単だけど$k$が一般だと難しい問題に対し、$k$が小さい場合にまで簡単さを拡張したい、というわけです。これまでにFPTアルゴリズムを作るための様々なテクニックが開発されてきましたが、その中で個人的に一番のお気に入りは半整数緩和を用いた分枝限定法です。
分枝限定法とは、答えの下界（or 上界)を何かしらの方法で計算して枝刈り探索する手法で、難しい問題を厳密に解きたい場合によく用いられるヒューリスティックです。近年の研究で、「半整数緩和」を持つ問題に対して、分枝限定法が唯のヒューリスティックではなく、$k:=$最適解$-$緩和解に対してFPTアルゴリズムとなることが分かってきました。直感的には緩和解が最適解と近ければ枝刈りが探索の浅いところで起きて高速に動きそうな気がしますが、この直感が正しいというわけです。
では、どういった問題が半整数緩和を持つのでしょうか？前研究「Half-integrality, LP-branching and FPT Algorithms (https://arxiv.org/abs/1310.2841)」では、$k$劣モジュラ性という劣モジュラ性の一般化を用いることで、unit propagationで解けるタイプの問題が半整数緩和を持つことを示し、FPTアルゴリズムを得ることに成功しました。また、最初の例にある二部グラフ判定・2-SATに対しては、緩和問題を最小カットに帰着して解くことで線形時間に出来るということも示しました。一方で、グラフが森かなど他の多くの性質に対してはそのような帰着が出来ず、緩和問題を解くために(指数サイズのLPなので）楕円体法を用いる必要がありました。これらの問題のうちいくつかは全く別の手法により各個撃破で線形時間が達成されましたが、他の問題に拡張出来ず、また$f(k)$の部分が非常に大きくなる、といった問題点がありました。
今回の研究の大きな動機となったのは、一つ前の記事で紹介しているFeedback Vertex Set (FVS)という問題を解くアルゴリズムの実性能を競うPACE challengeというコンペです。FVSは出来るだけ少ない個数の頂点を取り除いてグラフを森にするという問題で、まさに半整数緩和＋分枝限定法の枠組みが適用できる問題です。しかし先に述べたように、緩和解を求める既存手法が存在せず、そのままでは全く性能が出ませんでした。そこで、新たにFVSの半整数緩和を最大流っぽい増大路計算によって解く手法を開発し、コンペで優勝を果たしました。今回の手法はこの時のアイデアを元に、他の問題へ一般化したものとなっています。
