今回のトピックはグラフに対するNP-困難問題に対し, 「グラフクラスを制限することによって多項式時間で解く」アプローチについて広く浅く列挙します.
- 樹状幅を制限したグラフクラス (bounded tree-width)
樹状幅とはもともと, Robertson・Seymour によるグラフマイナー定理の証明に用いられた重要な概念であり, グラフの「木っぽさ」を表す指標になっています. グラフクラス(有限グラフの無限個の集合)として樹状幅がある定数で抑えられるようなクラスのことをbounded tree-widthと呼びますが, このクラスに対してはクラスカルの定理を用いることでマイナー順序がwell-quasi-orderであることを示し, そうでないクラスについては「樹状幅がboundできない」という情報からグラフの構造上の特徴を示し, 曲面に「だいたい」埋め込んだ後に色々して証明している(らしい)です.
一方でNP-困難な問題は木に対しては効率よく解けるということがよくあり, 例えば最大独立点集合問題は良い例です. したがって「木っぽい」グラフクラスであるbounded tree-widthに対しても最大独立点集合問題を効率よく解けるんじゃないか、という観点から研究が流行りました.
樹状幅が高々kであるようなグラフに対しては $O(2^k n)$ 時間で幅が小さい樹状分解を求めることができるので、$k$を定数とみなすとこれは線形時間になっています. これを用いて樹状分解上での動的計画法や分割統治法を用いて様々な問題を解きます. このような(樹状幅などのパラメータを定数とみなしたときに多項式時間で解けるかどうかを議論する)枠組みのことを FPT (Fixed-Parameter Tractability) といいます.
また, NP-困難な問題以外でも「グラフの直径の計算」「グラフの平均距離の計算」といったクラスPの問題(この２つの問題は $O(n^3)$ で解けるが $O(n^{2.999})$ 時間で解けるアルゴリズムが知られていない) に対しても同様のアプローチを考えることができて, 平均距離の計算を $O(2^{k \log (k)}\cdot n^{1+o(1)})$ 時間で行うアルゴリズムが2009年に提案されています. また, 2016年のSODAで FPT in P の概念が提唱され, (僕の中で)話題になりました.
- 平面的グラフ
グラフクラスを平面的グラフに限ると高速になるという話がたくさんあります. 例えばグラフの最大カット問題は一般にはNP-困難ですが, 平面グラフに対しては多項式時間で解くことができます.
一方でグラフクラスを平面的グラフに限ってもハミルトン閉路問題や最大独立点集合問題はなおNP-困難です. 平面的グラフ全体のクラスはbounded tree-width ではないので, 樹状幅によるFPTが通用しません. 実際, $k\times k$の格子グラフの樹状幅は$k$であることを示すことが出来ます.
平面的グラフの辺数は最大で$3n - 6$なので, スパースです. 辺数$m$のグラフの直径を$o(m^2)$ 時間で計算するアルゴリズムがSETHの仮定のもとで存在しないことが知られています. つまり, スパース(i.e. $m=O(n)$)なグラフの直径には(SETHのもとで)$\Omega(n^2)$時間が必要であることになります. しかし, 平面的グラフの直径・平均距離を $O(n^{11/7} \cdot \mathrm{poly}\log n)$ 時間で行うアルゴリズムが2017年に提案されています(この論文はSODA2017でBest Paper Awardを受賞).
- bounded local tree-width
bounded local tree-width というグラフクラスに触れます. このクラスに属すグラフ$G$ は次の条件を満たしています:
ある関数 $f(r)$ が存在して, 任意の頂点 $v$ に対して, $v$ から半径 $r$以内にある頂点から誘導される $G$の部分グラフの樹状幅 が $f(r)$ で上から抑えられている.
 |
| bounded local tree-width のイメージ. |
局所的な部分の樹状幅が functionally bounded であるということです. 実は平面的グラフは bounded local tree-width です. 実際, $f(r) = 3r-1$ が成り立ちます (この事実は全然自明じゃないです). また, bounded local tree-width なグラフ$G$に対しては $\mathrm{tw}(G) \leq f(\mathrm{diam})$ が成り立ちます. (ここで$\mathrm{diam})$は $G$ の直径です).
したがって, bounded local tree-width というグラフクラスは bounded tree-width を拡張して平面的グラフを含むようにしたというようなグラフクラスになっています. このクラスに対するFPTのような枠組みは僕はあまり見かけたことはありませんが, 面白い研究題材になるんじゃないかと思っています.
余談 : bounded tree-width と bounded local tree-width のマイナーによる特徴づけ.
グラフマイナー理論において, bounded tree-width をマイナーの言葉で特徴づけしている次の定理が知られています:
グラフクラス $\mathcal{C}$ が bounded tree-width でないことの必要十分条件は, 任意の平面的グラフ $H$ に対して$H$をマイナーとして含むグラフ $G\in \mathcal{C}$ が存在することである.
この定理は片方の向き (右から左) は自明です. 左の主張を仮定します. $H$ を $n\times n$ の格子グラフであるとすると, $H$をマイナーとして含む $G\in \mathcal{C}$ が存在しますが, $H$の樹状幅は$n$なので, $\mathrm{tw}(G)\leq n$ となります. $n$は任意にとれるので, $\mathcal{C}$は bounded tree-width ではありません.
この定理の凄いところは左から右です. 実は, 「任意の$n$に対してある$k$が存在して, 樹状幅$k$以上の任意のグラフは$n\times n$の格子グラフをマイナーとして含む」という定理が知られていて, 更に「任意の平面的グラフ$H$に対して$H$をマイナーとして含むような格子グラフ$H'$が存在する」ということが簡単に言えます. この２つの事実を組み合わせることによって左から右の主張を証明することができます. 左の主張を仮定します. 任意の平面的グラフ$H$に対してある$n$が存在して, $n\times n$ 格子グラフ$H'$は$H$をマイナーとして含みます. この $n$に対してある$k$が存在して, 樹状幅$\geq k$の任意のグラフは$H'$, すなわち$H$をマイナーとして含みます. 左の主張の仮定より, $\mathcal{C}$は樹状幅$\geq k$のグラフ$G$を必ず持つので, 右の主張における所望のグラフをこの$G$が得られます.
では, bounded local tree-width をマイナーの言葉で特徴づけすることはできるのでしょうか？ 実は, 次の定理が知られています[Eppstein, 2000]:
minor-closed なグラフクラス $\mathcal{C}$ が bounded local tree-width でないことの必要十分条件は, 任意のApex graph $H$ に対して$H$をマイナーとして含むグラフ $G \in \mathcal{C}$ が存在することである.
Apex graph とは, 「頂点を一つ取り除くことによって平面的になるようなグラフ」のことです. Apex graph の全体は平面的グラフを含みます. 例えば $n\times n$格子グラフに新たな頂点を一つ追加し, 新たな頂点を格子グラフの$n^2$個の頂点に接続して得られるグラフ$H$を考えましょう. このグラフは直径が2ですが, 樹状幅$=n$なので, bounded local tree-width ではありません. このことから定理の片方の向き (右から左) が言えます.
0 件のコメント:
コメントを投稿