0. 概要
以前の記事に紹介したグラフマイナー定理の証明において非常に重要な役割を担うのが木分解 (tree decomposition) という概念です.
木分解に関しては, 色んなサイト (例えばここ) やグラフ理論の本で取り上げられているので, 本記事では木幅の下界の示し方を紹介します. 具体的には, 木幅は minmax の形で定式化できるのですが, その双対となる茨数を maxmin の形で導入し, 強双対性が成り立つことを紹介します.
(＊): 個人的にはtree decompositionのことを「木っぽく」分解するという気持ちから樹状分解と心の中で呼んでいるのですが, ほとんどの方は木分解と呼んでいるのでそれに倣います.
1. 準備
1.1. グラフの定義
グラフ $G=(V,E)$ は無向とし, $E\subseteq \binom{V}{2}$ とする. $G$の頂点集合と辺集合をそれぞれ $V(G)$, $E(G)$ で表す. グラフ $H$ が $G$ の部分グラフであるとは, $V(H)\subseteq V(G)$ かつ $E(H)\subseteq V(G)$ が成り立つことをいう.
1.2 木分解・木幅の定義
グラフ $G$ に対し, 次の性質を満たす組 $(T, \mathcal{V})$ を $G$の木分解と言います.
まず $T$ は木で, $\mathcal{V}=(V_t)_{t \in V(T)}$ は, $T$の頂点 $t$ で添え字付けられた$G$の部分頂点集合族です. そして
1. $\bigcup_{t \in T} V_t = V(G)$.
2. $G$ の各辺 $e=\{x, y\}$ に対し, $\{x,y\}\subseteq V_t$ なる $t\in T$が存在する.
3. 任意の頂点 $v \in V(G)$ に対して, $T$の頂点部分集合 $\{t\in V(T):V_t\ni v\}$ が誘導する $T$ の部分グラフは連結である.
Proposition1.
グラフ $G$ の木分解 $(T,\mathcal{V})$ を任意にとってくる. ある $t\in V(T)$ が存在して, $G-V_t$の各連結成分の頂点数は高々 $|V(G)|/2$となる.
グラフ $G$ の木分解 $(T,\mathcal{V})$ を任意にとってくる. ある $t\in V(T)$ が存在して, $G-V_t$の各連結成分の頂点数は高々 $|V(G)|/2$となる.
Proposition 1に出てくる $V_t$のことをセパレータと呼んだりします. 木の場合はある頂点を取り除くと残った二つの連結成分のサイズを $n/2$ 以下にすることができますよね？それと同じ気分です. セパレータを使うと分割統治法とかが使えて良いアルゴリズムが設計しやすくなります.
上: 木分解のセパレータ 下:木のセパレータ
定義2 (木幅)
グラフ $G$ の 木幅 $\mathrm{tw}(G)$ は,
$$
\mathrm{tw}(G) = \min_{(T,\mathcal{V})}\max_{t\in V(T)} |V_t| - 1.
$$
グラフ $G$ の 木幅 $\mathrm{tw}(G)$ は,
$$
\mathrm{tw}(G) = \min_{(T,\mathcal{V})}\max_{t\in V(T)} |V_t| - 1.
$$
コメント.
木幅の定義式の $\min$ は$G$の全ての木分解をとります. よく知られるように, $G$が木である iff $\mathrm{tw}(G)=1$ となっており, $\mathrm{tw}(G)$ は $G$ の木っぽさを表す尺度になっています. 定義式の最後の -1 は本質的ではなく, 単に「木の木幅は1である」が成り立つようにするために導入されてるのだと思います (個人的には -1 がない方がいろいろと綺麗になるので良いとは思うのですが...).
2. 双対定理
2.1. 茨
定義3 (タッチ).
$G$をグラフとする. 二つの部分集合 $F_1,F_2\subseteq G$ が
・$V(F_1)\cap V(F_2)\neq \emptyset$, もしくは
・ある二つの頂点 $v_1\in V(F_1),\,v_2\in V(F_2)$ が存在して $\{v_1,v_2\}\in E(G)$
であるとき, タッチしているという.
$G$をグラフとする. 二つの部分集合 $F_1,F_2\subseteq G$ が
・$V(F_1)\cap V(F_2)\neq \emptyset$, もしくは
・ある二つの頂点 $v_1\in V(F_1),\,v_2\in V(F_2)$ が存在して $\{v_1,v_2\}\in E(G)$
であるとき, タッチしているという.
定義4 (茨).
グラフ $G$ の部分グラフの族 $\mathcal{B}=\{B_1,\ldots,B_m\}$ が以下の条件全てを満たすとき, $\mathcal{B}$ を 茨 という:
・各 $B_i$ は 連結グラフである.
・どの $i,j\in\{1,\ldots,m\}$ に対して $B_i$ と $B_j$ はタッチしている.
グラフ $G$ の部分グラフの族 $\mathcal{B}=\{B_1,\ldots,B_m\}$ が以下の条件全てを満たすとき, $\mathcal{B}$ を 茨 という:
・各 $B_i$ は 連結グラフである.
・どの $i,j\in\{1,\ldots,m\}$ に対して $B_i$ と $B_j$ はタッチしている.
定義5 (カバー).
グラフ$G$ の部分グラフ族 $\mathcal{B}=\{B_1,\ldots,B_m\}$ を考える. 頂点部分集合 $C$ が $\mathcal{B}$ をカバーしているとは, すべての $i=1,\ldots,m$ に対して $C\cap B_i\neq \emptyset$ を満たすことをいう. この$C$を$\mathcal{B}$のカバー集合とよぶ. $\mathcal{B}$ のオーダーを, $\mathcal{B}$ のカバー集合のうち最小サイズとする.
グラフ$G$ の部分グラフ族 $\mathcal{B}=\{B_1,\ldots,B_m\}$ を考える. 頂点部分集合 $C$ が $\mathcal{B}$ をカバーしているとは, すべての $i=1,\ldots,m$ に対して $C\cap B_i\neq \emptyset$ を満たすことをいう. この$C$を$\mathcal{B}$のカバー集合とよぶ. $\mathcal{B}$ のオーダーを, $\mathcal{B}$ のカバー集合のうち最小サイズとする.
定義6 (茨数).
グラフ $G$ の茨数 $\mathrm{br}(G)$ を, $G$の茨の中での最大オーダーで定める. すなわち
$$
\mathrm{br}(G) = \max_{\mathcal{B}}\min_{C} |C|
$$
である ($\mathcal{B}$ は $G$ の茨全体, $C$ は $\mathcal{B}$ のカバー全体を動く).
グラフ $G$ の茨数 $\mathrm{br}(G)$ を, $G$の茨の中での最大オーダーで定める. すなわち
$$
\mathrm{br}(G) = \max_{\mathcal{B}}\min_{C} |C|
$$
である ($\mathcal{B}$ は $G$ の茨全体, $C$ は $\mathcal{B}$ のカバー全体を動く).
例 (グリッドグラフ)
$n\times n$ のグリッドグラフ $G$ を考えます. 下図のような頂点部分集合$B_{ij}$を十字集合と呼ぶことにします.
図1. 茨の例
フォーマルな定義は, グリッドグラフ $G$ の頂点集合が $V(G)=\{(i,j):i,j\in [n]\}$ だとすると, $B_{ij} = \{(y,x):y=i \text{ or }x=j\}$ となります. ここで, $\mathcal{B}=\{B_{ij}\}_{i,j}$ は 茨 になっていることがわかると思います. また, 図右のように, 頂点集合 $\{(i,i)\}_{i=1}^n$ はこの $\mathcal{B}$ のカバーになっていることが分かります. つまり, $\mathrm{br}(G)\geq n$ が分かります.
2.1. 双対定理
木幅と茨数に関する以下の双対定理が成り立ちます.
定理8 (強双対性) [Seymour, Thomas, 1993]
任意の連結グラフ $G$ に対し
$$
\min_{(T,\mathcal{V})} \max_{t\in V(T)} |V_t| = \max_{\mathcal{B}}\min_{C} |C|
$$
すなわち, $\mathrm{br}(G)=\mathrm{tw}(G)+1$.
任意の連結グラフ $G$ に対し
$$
\min_{(T,\mathcal{V})} \max_{t\in V(T)} |V_t| = \max_{\mathcal{B}}\min_{C} |C|
$$
すなわち, $\mathrm{br}(G)=\mathrm{tw}(G)+1$.
コメント (NP=coNP ?).
木幅の計算はNP困難であることが知られており, 木幅$\leq k$ かどうかの判定問題は NP完全です. 一方で定理7を見ると木幅$\geq k'$であることの witness として茨を考えれば良いじゃないかという気もしてきます. ということは, 木幅$\leq k$の判定問題は coNP に属す, すなわち NP=coNP の証明になってしまうのではないか？ ということが気になります. 結論からいう茨そのものは指数サイズになりえるため答えはノーです.
定理8の証明はDiestelのグラフ理論の和訳されたものに載っています. 自分はM2の夏に読んだのですが, 少し長くて大変だった記憶があります.
2.2 例 (グリッドグラフ)
先ほど $n\times n$ のグリッドグラフ $G$ を考えていました. オーダー $n$ の茨を構成していたので, $\mathrm{tw}(G)\geq n-1$ が示されたことになります.
実は, $\mathrm{tw}(G)=n$ になります. というのも木分解として
図2. 最適な木分解 (パス分解にもなる)
このように与えることができます (この木分解により, $\mathrm{tw}(G)\leq n$が言える).
一方で, 最適な茨としては
図3. 最適な茨
図1の青を上図のようにちょっと修正したもので与えられます.
3. 結論
オーダーの高い茨が構成できれば, 木幅の下界を示すことができます. これであなたも立派なグラフマイナー研究者ですね!
0 件のコメント:
コメントを投稿