近似アルゴリズムのお話し: Baker's technique
今年もデータ構造とアルゴリズムアドベントカレンダーの季節になってきました．これはカレンダー12日目の記事ですね．個人的な話ですが，去年度にようやく長い長い学生生活を終えたので，今年は隣の分野くらいのことをちゃんと勉強してみたいなぁと思い，いろいろ漁って勉強しました．TLの皆さんにはいろんな有用情報をいただいてありがとうございました！「このツイートしたら誰かいい情報教えてくれないかなぁ」と期待してツイートしたことが何度もありました．
そんなこんなで興味あったけどちゃんと勉強していなかったマトロイド，近似アルゴリズム，乱択アルゴリズムあたりをちゃんと本買って読んでみるか〜と思い，最初の1章とそれ以外を1つくらいは読んで，完全に理解しました．その中で，近似アルゴリズムが一番わかった感が強いので，自分の復習も兼ねて，近似アルゴリズムでよく使われるテクニックを1つ紹介しようかと思います．ちなみに僕は近似アルゴリズムを[1]で勉強して，今回は[2]の論文のテクニックを紹介します．
今回紹介するテクニックは1994年に発明されたBaker's techniqueとよばれるアルゴリズム構築技法です．これは入力が平面グラフのときに，最大独立点集合問題や，最小頂点被覆問題，最小支配集合問題といったNP-完全な問題に対し，PTAS（polynomial time approximation schem）を与えるアルゴリズム構築技法です．今の一文で未定義用語が5つくらい出ましたね．問題の名前はいいとしても，平面グラフと，NP-完全，PTASあたりは説明が必要かと思います．なので，次にそれらの用語の説明を簡単にします．
用語と今回の目標の説明
今回出てくる用語について簡単に定義します．正確でない定義も多々ありますので，正確な定義が知りたい方は申し訳ないですが，参考文献の方を見てください．
- 平面グラフ: 平面に辺の交差がなく描けるグラフのことです．グリッドなんかは平面グラフですね！正確には平面的グラフという気がしますが，今回は平面グラフと読んでしまいます．これはplanar graphとplane graphは実はちょっと違うという話と関係あると思っています．
- NP-完全問題: これは正確な定義がかなりややこしいので，ここではかなり多くの嘘を含みますが，多項式時間で解けないと信じられている問題の集合くらいに思ってくれれば大丈夫だと思います（プロの方が見ていたら生暖かい目で見逃してください）．
- PTAS: これは近似アルゴリズム分野の用語で，次のような条件を満たすアルゴリズムをPTASとよびます．最大化問題$\Pi$に対し，入力$I$とエラーパラメータ$\epsilon$（$\epsilon$は定数とみなす）が与えられたとき，最適解の値を$OPT$とすると，$(1 - \epsilon)OPT$を多項式時間で計算するアルゴリズム．
最小化問題に対するPTASは$(1-\epsilon)$が$(1 + \epsilon)$になります．計算時間の具体例としては，$O(|I|^{1/\epsilon})$時間と言った計算時間です．この時間で動作するアルゴリズムは$\epsilon$が定数なので，多項式時間で動作するとみなします．このとき，特に$|I|$と$1/\epsilon$の両方に関して多項式時間で動作するアルゴリズムはFPTAS（fully polynomial time approximation scheme）とよばれます．ナップサック問題なんかはFPTASを持つ問題の典型ですね．なので，この話を最大独立点集合問題を例に当てはめると，入力$I$が平面グラフ$G$で，エラーパラメータ$\epsilon$が与えられたときに，PTASを達成するアルゴリズムを与えます *1 *2
ちょっとした注意
この記事で紹介する方法では何度か木幅というグラフのパラメータを計算する必要があります．しかし，僕は実は木幅の厳密計算を理解していないので，今回の記事に書いてある方法だけでは近似アルゴリズムを作れません．しかし，入力グラフの木幅の値 $tw$ が$\epsilon$ を定数としたときに，定数であることが示せることと，定数 $k$ に対して，幅が $k$ 以下の木分解を計算する or 幅が $k$ 以上だと返すのは「線形時間」[6] *3でできるので，木幅は線形時間で計算可能だと思って記事を書いています．本音を言うとちゃんと元論文を読めばグラフの性質を使って線形時間で木幅がもっと簡単に厳密計算できそうに見えるのですが，まだそこまで理解していないです．ごめんなさい*4．
Baker's techniqueの概要
Baker's techniqueは現代の知識，特に木幅DPの知識を持ってみると実はすごい簡単なテクニックです．木幅に関するDPはきっと15日のゆらふなさんが書いてくれると思うので，今回はDPの詳細は省略しますが，木幅の定義は与えます．
大雑把にいうとBaker's techniqueは次のようなアルゴリズム構成法です．平面グラフ$G$の任意の頂点$v$を始点とし，$v$からの距離によって頂点を $V_0 = \{ v \}, V_1 , \ldots, V_{ n-1 } $ に頂点を分割します．この分割において，整数$j < k$に対し，$\bigcup_{ 0 \le i \le n/k } V_{ ik + j }$を削除します．直感的に言うと，距離 $k$ ごとにその距離を持つ頂点を全部消すと言う操作です．すると，グラフがいくつかの連結成分に分解されるのですが，実はこれらの連結成分は$k$-outerplanar graphと言い，$k$ が定数ならば，多くの難しい問題が簡単に解けがちなグラフになります．実際，$k$-outerplanar graph上では最大独立点集合は線形時間で計算できます．なので，このそれぞれの$k$-outerplanar graph上で，最大独立点集合を計算し，その和集合である独立点集合は実は良い近似比を達成すると言うテクニックです．そして，この $k$ の値を$1/\epsilon$ に設定すると近似比が $(1-\epsilon)OPT$ になり，計算時間も$n$ と定数$1/\epsilon$ に対して多項式時間になるので，PTASを達成します．
$k$-outerplanar graph 上での最大独立点集合問題
次に $k$-outerplanar graph の定義と，なぜ $k$-outerplanar graph上なら最大独立点集合が線形時間で解けるかを説明します．まずは定義からです．$k = 1$の時，つまり $1$-outerplanar graphはouterplanar graphともよばれ，平面描画するときに，全ての頂点が外面と接する様に平面描画できる平面グラフです．さらに，$k$-outerplanar graphとは平面描画したときに，外面と接する頂点を削除するという操作をすると $k - 1$ -outerplanar graphになるグラフです．$k$-outerplanar graphの具体例は次のようなグラフです．
このグラフだと外面に接する頂点削除を2回繰り返すとグラフが空にできるので，$2$-outerplanar graphです．
次に，平面グラフと $k$-outerplanar graph の関係を考えます． まず，平面グラフ中の頂点 $v$ に対し，先程の距離ごとに頂点集合を分割するルールを適用すると次のようになります．以下の例では 中心の頂点 $v$ を 頂点1にしています．
今回は$k=2$，つまり，$v$ からの距離が偶数の頂点を消した時の例を描いてみましたが，$k$を一般の場合にしてもだいたいこのように，中心から同心円状に頂点がのび，階層が$k$回に1回削除されるという構造になります．これをみると，削除されなかった頂点からなるグラフは，平面グラフの平面描画を考えると，外面に接する頂点削除を$k$回行うと空にできるので，これは$k$-outerpalar graphになります．
次に，$k$-outerplanar graphの木幅について考えます．木幅のお話は結構有名なので，他のブログにもありますね．
それと日本語wikiもあります．
あと，電気通信大学の授業もおすすめです．
http://dopal.cs.uec.ac.jp/okamotoy/lect/2016/treewidth/handout06.pdf
せっかくなので，電通大の授業スライドから定義を借りてくると，木分解の定義は次のようになります．
グラフ $G = (V, E)$ に対して，次の木 $\mathcal T$ を$G$ の木分解という
- $\mathcal T$ のノードは$V$の部分集合
- 各辺 $\set{u, v} \in E$に対し， $\set{u, v} \subseteq X$となるノード$X$が存在する．
- 各頂点 $v \in V$ に対し， $\mathcal T$ で $v$を含むノード$X$からなる誘導部分グラフは木になる．
具体例はwikiとか授業スライドを見るとわかりやすいと思います． ここで，ノード$X$の頂点数の最大値を$\mathcal T$の幅といいます．この条件を満たす分解はたくさんある（自明な木分解は$\mathcal T$が1ノードからなる木で，そのノードが全ての頂点を含む時）のですが，幅が最小である木分解の幅を$G$の木幅といいます． そして，実は$k$-outerplanarの木幅は $3k-1$ 以下であることが知られています[3]．
木幅が小さいグラフというのはめちゃくちゃ嬉しい性質が知られています．それはCourcelleの定理と呼ばれているのですが，次のような激ツヨ定理が知られています．
- 入力グラフ $G$ 木幅が定数であり，MSO（monadic second order logic）式 $\phi(X)$ が与えられた時，$\phi(X)$ を満たす要素数最大の $X$ は線形時間で発見できる．*5
MSOについてはここを参考にするといい感じです*6． 独立点集合は次のMSO式で書くことができます．
$\phi(X) = \forall u \in X( \forall v \in X( \set{u, v} \not\in E)$
この「MSOで記述できれば線形時間で解ける」という結果は激ムズなんですが，個々にアルゴリズムを作るのはそんなに難しくないことが多いです． きっとゆらふなさんの記事を読めば解けるようになると信じています． 大雑把には木分解の木があるので，その木の葉っぱからDPをするのですが，1ノードごとに状態数が$2^{k}$状態あるのでそれを全部覚えながらDPする感じです．なので，詳細は省きますが，独立点集合なら（確か） $O(2^{k} k^{2} n)$ 時間で解けます*7．今木幅は$3k-1$以下なので，$k = 1/\epsilon$に設定すると，この計算時間は $O(8^{1/\epsilon} (1/\epsilon)^{2} n)$ 時間になりますね．これをそれぞれの連結成分ごとに計算するので，総和は同じ計算時間で抑えられます．最後に，どの距離の頂点集合を削除するかが $k$ 通りあるので，$k = 1/\epsilon$回繰り返すため，全体の計算時間は $O(8^{1/\epsilon} (1/\epsilon)^{3} n)$ になります（注意: 木分解を計算する時間は考慮に入れていないです．）．これで計算時間はPTASの定義を満たしていますね！
あとは今計算した独立点集合の和集合がちゃんとサイズ$(1 - \epsilon)OPT$ 以上を達成するかどうかという近似比についての議論します．
アルゴリズムの近似比の解析
まずアルゴリズムの近似比の解析のために$S$を$G$中の最大独立点集合とします．今，グラフの分割をいくつか試しているので，分割の中で最も$| S \cap \bigcup_{0 \le i \le n/k}V_{ik + j}|$が小さい$j$ではサイズが$|S|/k$以下になります．実際にどの$j$がサイズを最小にするかはわからないのですが，これは全通り試しても$k$通りしかないため，これは全通り試し，サイズが最大な独立点集合を出力すればサイズを最大にする $j$ は見つけられます． したがって，得られる独立点集合のサイズは$(1 - 1/k) OPT$となります．よって，$k = 1/\epsilon$とすれば，近似比は$(1 - \epsilon)$を達成します．
Baker's techinqueの発展
平面グラフに対する効率良いアルゴリズムはかなり昔から研究されていて，グラフアルゴリズムの中心的な分野と言っても良いと思います．正直怖いのであまり手を出したくなかったのですが，これは意外と簡単だったので，ちょっと興味が出てきました．Baker's techniqueも90年代のテクニックだし， 平面グラフ上のアルゴリズムというメジャーなトピックなので，いろいろ発展系が研究されている様です．この辺りは本当によく知らないのですが，グラフの平面さを表すcrossing number（平面描画した時の辺の最小交差数）あたりでは研究がある様です[4]．それと風の噂によると，Bidimensionalityというのも発展系っぽいというのを聞きました[5]．なんか$k \times k$のグリッドグラフをマイナーとして含まないようなグラフに対するDPっぽいです．（あんまりわかっていない．）
なんかBaker's techniqueは結構簡単なテクニックかとおもっていたのですが，こうやって書いてみるとそれなりにいろんな知識が必要ですね．
参考文献
[1] Vazirani, Vijay V. Approximation algorithms. Springer Science & Business Media, 2013.
[2] Baker, Brenda S. "Approximation algorithms for NP-complete problems on planar graphs." Journal of the ACM (JACM) 41.1 (1994): 153-180.
[3] Bodlaender, Hans L. "A partial k-arboretum of graphs with bounded treewidth." Theoretical computer science 209.1-2 (1998): 1-45.
[4] Grigoriev, Alexander, and Hans L. Bodlaender. "Algorithms for graphs embeddable with few crossings per edge." Algorithmica 49.1 (2007): 1-11.
[5] Cygan, Marek, et al. Parameterized algorithms. Vol. 4. No. 8. Cham: Springer, 2015.
[6] Bodlaender, Hans L. "A linear-time algorithm for finding tree-decompositions of small treewidth." SIAM Journal on computing 25.6 (1996): 1305-1317.
*1:元論文は $O(8^{1/\epsilon} (n + m) )$ で，僕の今回のアルゴリズムは $O(2^{2^{1/\epsilon}} (1/\epsilon)^{3} n)$ くらいなので，めっちゃ負けていますが，PTASにはなります．
*2:木幅計算パートを無視すると，$O(8^{1/\epsilon} (1/\epsilon)^{3} n)$ になります．
*3:定数項がえげつないです．ざっと見積もっても $2^{2^{k}}$ は軽くあります
*4:PTASを与えると言う結果には矛盾しないので許してください！
*5:記述が間違っていたらごめんなさい
*6:この授業スライドは他のトピックも非常に面白いので，おすすめです．僕はマトロイドも結構ここのスライドで勉強しました．
*7:$k^{2}$ の部分が自信ないですが，$poly(k)$ なのは間違い無いです．
