読者です 読者をやめる 読者になる 読者になる

wataの日記

プロコンや研究の話など書くかも

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$を含まないようなものの大きさの下界を与えており,以下のような性質を持っています.

  1. 最適解で $0$, $\frac{1}{2}$, $1$ のみの値を取るものが存在する (Half-integrality)
  2. 最適半整数解を $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)

ICFPC 2016 参加記

運悪く日程が被ったDCJ決勝は棄権し今年もいつものチームでICFPCに参加.メンバーと役割分担,問題概要はchokudaiの記事を参照.ソルバの実行結果ログなどから思い出したところによると,以下の様に3日間作業した.

 

一日目(Lightning)

公式Twitterの発言から関数型ゲーかと思いきや,折り紙の折り方を求める問題だった.foldつながり?各チームが解答と問題を両方提出し,他のチームの問題を沢山解けば解くほど,自分のチームの問題が解かれなければ解かれないほどスコアが高いという形式で,ICFPCに本気で挑むキッカケともなった2010年を思い出した.この形式はジャッジの好みに影響されない公平感があって好き.折り紙に関する理論研究が色々あることは有名な事実なので,とりあえず論文をググったりしたが,直接役に立ちそうな知見は得られなかった.

 

問題を読んでchokudai&iwiらと相談しながら,全体の戦略を練る.スコアの計算式から厳密解と近似解の間に物凄い差があり厳密ソルバが必須であろうということと,二日目から一時間に一問ずつ問題を出題出来るという仕組みから,初日のうちに小さくて激ムズな問題を作成する必要があることが分かる.解答サイズを制限ギリギリにすることでショートコーディング必須ゲーに出来るのでは…と危惧していたが,スコアに影響するのは問題サイズではなく模範解答のサイズであることが発覚し,そういう問題は出題する旨味がほぼゼロなので安心した.が,勘違いしたままのチームが居たのかショートコーディングゲーな問題がチラホラあった.

 

とりあえず,無限に時間があれば厳密解が求まる手法を考えることにする.公式ビジュアライザで遊んでいたら,鶴を折るためには広げる操作が必要なので単純な折り曲げ操作しか出来ない公式ビジュアライザでは不可能なことが発覚する.広げ方のパターンを色々搭載しても複雑な折り方をされたら解けなくね…と色々考えているうちに,実際に紙を折っていったり,折られた状態から戻していくという方針ではなく,Skeletonの各面を正方形に敷き詰めていく探索(例えばSkeleton上で面Aと面Bが辺aで接している時,展開した状態で面Aに対応するパーツがどこかにあり,それに辺aを介して隣接するのは面Bもしくは辺aに関して反転させた面Aのどちらかなので二通りに分岐するという感じ)をすればどんな複雑な折り方をされても無限に時間があれば解けそうという結論に至り,それを実装することにした.

 

今年も相変わらず,複数人で協力して一つの言語で一つのソルバを書くということはしなかったが,入力が結構使いにくい形式で,全部一人でやるのは大変&自分とchokudaiのソルバの両方で同じ処理が必要そうということで,iwiが線分アレンジメントなどの面倒な前処理と,出力を短くする後処理をするプログラムをC++で作成し,それに自分のJavaソルバやchokudaiのC#ソルバがサンドイッチされて実行されるというカオス仕様になった.多倍長分数ライブラリや幾何ライブラリは当然予め用意してあったが,実数使わずに分数のままで回転させたり反転させたりする操作が激しく難しかったのでtosに教えてもらって実装.この関数はchokudaiのC#ソルバ(と確かC++)にも移植されて使われた.

 

ログによると初日の0:00にはソルバは一通り出来上がっていて,この時点で古事記(ジャッジの用意した問題)を1問あたりの制限時間1分で101問中50問解けたらしい.この時点でのアルゴリズムは,まず角に接するSkeletonの面を一つ適当に選んでスタートし,各辺に対して折る(=面を反転させて置く)か折らない(=Skeleton上で隣接する面をそのまま置く)かの二通りで分岐していく探索.既においた面と重なるようには置くことが出来ず,二通りどちらの置き方も出来ない,もしくは残りの面積がまだ使っていないSkeletonの面積を下回ったら枝刈りを行う.できるだけ浅い所で枝刈りをしたいので,置けるかの判定は分岐する1辺のみで行うのではなく,全ての未処理の辺について各探索ノードで毎回行った.更に,もし1通りしか置き方がないと分かった辺があれば分岐せずに先にそこを決めた.探索順序は割と適当で,最初に角に置く面はランダムに選び,分岐はまだ使っていないSkeletonの面が使えるものを優先した.

 

デバッグと探索の改良のために,昔ICPC用に作った幾何問題用簡易ビジュアライザを使って探索の様子を動的に見れるようにしたところ,通常,探索アルゴリズムは間違った方向を深く探索してしまうのを避けるために,制限時間を長くするよりも探索順を変えて何度も探索したほうが効率的な場合が多いのだが(例えばSAT Solverのrestart),今回の場合はそもそも多倍長有理数幾何が重すぎる上に,枝刈り判定のために毎ノードで大量に幾何計算を行っていてほぼバックトラックなしのストレートで探索が進んでいても制限時間内に終了していないことが発覚.試しに制限時間を10分に増やした所,解ける問題数が60問に増えたので高速化を開始.重たい多倍長有理数計算を避けるために,各面にdoubleでbounding boxを持たせ,衝突判定時に先にbounding box同士が衝突しているかの判定を行って衝突しないものはスキップしたところ爆速になって問題数が71問に増えた.

 

問題をよく見てみると,最初に横に何回か折りたたんで長方形にしてから残りを折るものが結構あることが分かったので,次はそういう問題用の機能を搭載することにする.辺の長さから何分の一の長方形にしたら良いかの候補を列挙し(長さ1/dの辺があったら1×1/dの長方形を試すことにした),正方形に埋め込む代わりに長方形に埋め込んでから最後にそれを正方形に戻せば良い.この拡張により解ける古事記問題が78問に増えた.

 

ここまでで9:00になってLightningが終了.自分のソルバは凸多角形のような簡単なものでも解けないのがあったのでchokudaiが凸ソルバを作って解けなかった問題を拾ったり,一部手作業で解けたものなども提出した.9:00の時点の順位表でトップになって喜んでいたら9:00に公開された各チームの提出問題分のスコアが含まれていることが発覚し,その分のスコアを抜いてみたら実は2位で残念だった.他の上位チームも結構接戦で皆探索書くの速いなあと思っていたが,実は手作業で解いているチームが多かったっぽい.

 

二日目〜三日目 

Lightningが終わって各チームが問題を出題出来るようになった.我々のチームは初日のうちにtosが激ムズ問題生成器を開発し,それの出力を人の目で見て更に選別して難しそうなのを出題した.tos作の出題した問題ビジュアライザ: http://tosk.jp/icfpc2016/viewer.html

 

他のチームの出題した問題にすぐに解答を送ることも出来るが,出題した問題が解かれたらより難しい問題を次は出題してくることが予想されるため,出来るだけ他のチームが我々の解ける簡単な問題を出題し続けてくれるよう,正答数3未満の問題には解答を提出しないという潜伏作戦を取ることにした.

 

他のチームの問題を見ていたら一見簡単そうに見える問題で細かい面が大量発生しているせいで正方形に埋め込んだ時の面の個数が爆発し衝突判定が相変わらず爆遅であることが発覚.毎回全ての辺について二通り試して衝突判定するのは時間がかかりすぎてヤバイ(各探索ノードで辺の数×面の数回の衝突判定)ので,新しい面を置いたら各辺について二通りそれぞれ今置いた面と衝突するかを判定するようにした(各探索ノードで辺の数回の衝突判定に改善).この高速化で古事記の解ける問題数が87問に増えた.

 

探索順序がかなり適当だったので改良しようと色々試したがあまりうまく行かず,特に最初の一手を間違えると絶望するケースが多数.そこで,四角形の周囲に来る辺の長さは有理数かつ和が1にならなければならないという強い制約から周囲の辺が埋まるのではないかという議論になり,iwiが正方形の周囲に来る辺の列を探すプログラムを書き,そのヒント情報(角の一頂点から周囲4辺全てまで任意の長さの辺列)を受け取ってヒントの続きから問題を解けるようにソルバを改良した.一部の問題では周囲の辺列がほぼ一意に求まって解くことが出来たが,候補が大量にあって使えないケースが多かった.しかし,プログラムには分からなくても,目で見たら角に来そうな頂点が分かる問題が結構あったので,手作業で四角形の周囲に来る辺列を求めるGUIをsulume&iwiが作成し,人力で作成したヒントによって解ける問題数が大幅に増加した.

www.youtube.com

 

ヒントを与えた場合,普通に探索した場合と違って初期状態で正方形のあちこちに面が置かれるため,探索の深い所で発見した矛盾が探索の浅い所での決定の影響を受けていない場合が非常に多くなる.例えば極端な例として,正方形が完全に分断されて二つの独立な問題AとBになったとし,Aは大量に解が存在するがBには一切解が存在しないとしよう.Bを先に探索した場合にはBに解がないと分かった時点でAを探索することなく終了出来るが,Aを先に探索した場合,まずAの解aを見つけ,Bの探索に失敗し,次にAの解bを見つけ,やはりBの探索に失敗し,…とAの解の個数回だけBの探索を行う必要が生じる.AとBは独立なのでAに対するどの解を採用しようともBの探索は必ず失敗するので,Aから先に探索した場合でも最初のBの探索失敗時にやはり終了して良いはずである.そこでConflict Analysisを行って,矛盾が探索のどの決定に依存しているかを解析することにより,矛盾を解消可能な地点まで一気にbackjumpするのを実装した.このテクは昔Marathon Matchで使ったやつ(http://d.hatena.ne.jp/wata_orz/20100805/1281000288)で,ヒントなしだとほとんど性能は変わらなかったが(古事記は相変わらず87問),ヒントありの場合の性能が飛躍的に向上した.ここまででついに古事記最終防衛問題と思われる鶴を倒すことに成功した.

www.youtube.com

↑ 見返してみると結構無駄が多いしまだまだ改善できそう

 

最終日0:00になり,解答を提出しない正答数のラインを3問未満→2問未満→1問未満→制限なしと徐々に緩めながら潜伏を解除することにした.自分のソルバの他にchokudaiが凸っぽい奴やショートコーディング問題や過去問回転させたやつなどを倒していき,解けない問題数は既に二桁になっていた.スコアボード凍結の3:00の時点では二位にトリプルスコア近い差を付けることが出来た.

 

 

 

Conflict解析を行ってもまだ数問だけ周囲4辺のヒントを完全に与えても解けない問題があったので,SAT Solverの技術を更に取り入れてソルバを改良しようとしたが,これはうまく行かなかった.そうこうしているうちに手動ヒント勢が問題を次々と倒していき全完が近づいてきたので,ソルバの改良は諦め,問題ごとにビジュアライザを眺めながら手動で良い方向に探索するようパラメータ調整することにより,ヒントありでも解けなかった問題を全て倒すことに成功した.

 

ラスト1時間半くらいでついに残りの問題数が一桁になり,全力で残りの問題のヒントを作成したが,惜しくも一問だけ残ってしまったorz 最後の問題は並行な線で非常に細かく大量に折りたたまれていて,一辺だけのヒントを与えた状態で,正方形を100.00% (小数点第三位四捨五入)埋めることに成功したよとソルバが出力しているのにも関わらず,超細かいパーツが埋まっていないらしく答えにはたどり着かず,二辺のヒントを与えれば解けそうなのに頑張っても手動でヒントが作れない…という状況だった.

  

 

感想

このチームでの参加も4年目くらいで大分慣れて来た感じがある.スコアボード凍結時点ではトップだったし,優勝出来ていると良いなあ… 最終結果は9/20に発表されるらしいです.相変わらずプログラミング言語の会議主催にも関わらずチーム内で使っている言語がバラバラだが,これはつまりタスクに合わせて適材適所で言語を選択するのが最適ということで… 最近はコンテスト引退気味だけどチーム戦はやはり楽しく,今年は問題も運営もしっかりしていて3日間楽しむことが出来た.運営の方々もありがとうございました.最近は研究の方でSAT Solver系のことにも手を出していて,上のソルバの動作とか見るとまだまだ改善の余地があるし,そのうち気が向いたらSAT Solverに学ぶ探索高速化術の解説を書くかも?