三角形・四角形を含まないグラフ(極値グラフ理論)

0. 概要

グラフ理論の中に「極値グラフ理論 (extremal graph theory)」と呼ばれる分野があります. 極値グラフ理論では, 「与えられた性質$\mathcal{P}$を満たすグラフのうち, 最大辺数を求める」ことを考えます. 極値グラフ理論で最も有名な結果はおそらくTuranの定理でしょう. これは, 性質$\mathcal{P}$を「サイズ$r$の完全グラフ$K_r$を含まない」としたとき, 辺数が最大のグラフは$r-1$部完全グラフであるという結果です.

気持ちとしては, 「どれほどの辺数を持てばグラフが性質$\mathcal{P}$を満たすことを保証できるか」という問題について考えるのが極値グラフ理論です.

1. Triangle-free グラフ

「三角形($=K_3$)を含まない」という性質を満たすグラフのうち最大辺数を持つグラフを考えます. (このようなグラフをtriangle-freeグラフといいます). こちらのページで紹介されているように(またはTuranの定理の帰結として), 完全二部グラフを考えると, 三角形を含まないような頂点数$n$のグラフが持ちうる辺数はおおよそ, 高々$\frac{n^2}{4}=O(n^2)$となります.

2. Triangle & Square-free グラフ

では, 「三角形・四角形を含まない」という性質を満たすグラフの最大辺数について考えます. 結論から言うとこのような性質を持つ頂点数$n$のグラフの辺数は高々$O(n^{1.5})$となることが示せます. 「奇数長の閉路を含まない」という制約を考えても完全二部グラフがとれるので, 辺数が$O(n^2)$になります. しかし四角形の制約を付け加えるだけでオーダーが劇的に下がる, という点が面白い点です. この結果はとても簡単に証明できるので, 紹介します.

定理. 三角形及び四角形を含まない$n$頂点のグラフ$G$の辺数は高々 $\frac{n\sqrt{n-1}}{2}$ である.

証明.
$G=(V,E)$を三角形・四角形を含まない$n$頂点のグラフとします. このグラフが含む長さ2のパスの本数を二通りの方法で数えます:

図のように, 頂点$v$を一つ選んだときに$v$を真ん中の頂点として持つような長さ2のパスを考えます. そのようなパスの個数は$v$に対して$i,j$の選び方の総数に等しいので, $\binom{d_v}{2}=\frac{d_v(d_v-1)}{2}$となります. ここで$d_v$は頂点$v$の次数です.
従って, 長さ2のパスの総数は



となります.


一方, $G$が四角形を含まないため, 隣接していない二頂点$i,j$を選択したときに, $i,j$を端点として持つような長さ2のパスは高々1本となります (下図). 従って, 長さ2のパスの本数は非隣接的な二頂点の選び方の総数, 即ち$\binom{n}{2}-|E|$で上から抑えることが出来ます.

非隣接頂点対$i,j$に対して, $i$と$j$の両方と隣接している頂点は高々一つである.

従って



よって,

                    ...(1)

となります.


次にコーシーシュワルツの不等式を用います. コーシーシュワルツの不等式は

$\left(\sum_v x_v y_v\right)^2 \leq \left(\sum_v x_v^2\right)\left(\sum_v y_v^2\right)$

ですが, これに$x_v=d_v$, $y_v=1$を代入すると

$4|E|^2 = \left(\sum_v d_v\right)^2 \leq n\sum_v d_v^2$                    ...(2)


(1)(2)より,

$\frac{4|E|^2}{n}\leq \sum_v d_v^2 \leq n(n-1)$

従って,

$|E| \leq \frac{\sqrt{n^3-n}}{2} = \frac{n\sqrt{n-1}}{2}$. (証明終)

3. 不等式はタイトなのか？

結論から言うとタイトです. こちらの記事で紹介したMoore graphを考えます. Moore graph は頂点数$k^2+1$の$k$-正則グラフで, かつ三角形・四角形を含まない($\iff$ 直径$=2$)ものです. Moore graph は $k=2,3,7$に対しては存在しますが, これら三つのグラフは辺数が$\frac{kn}{2}=\frac{k^3+k}{2}$となりますが, この値は辺数の上界$\frac{n\sqrt{n-1}}{2}=\frac{(k^2+1)k}{2}$となり, 辺数と等しくなっています.

強正則グラフのスペクトル解析と未解決問題への応用

0. 背景

グラフ理論とは文字通り, グラフについて解析する分野です. グラフ理論のモチベーションとしては, 「最小全域木」「最大マッチング」「最大フロー」などのアルゴリズムを考える際に対象となるオブジェクト(この例で言えば全域木, マッチング, フロー)に対する「良い」特徴付けや性質(例えばHallの結婚定理, グラフマトロイドの基, 交互増加道, 残余ネットワークに関するものなど)を与えるという, アルゴリズム上のモチベーションが最も大きいんじゃないかと思います.

しかしそれとは別に純粋数学寄りな一面もあります. グラフ理論の一分野に「Algebraic graph theory」というのがあります. 直訳すると「代数的グラフ理論」で, この分野はグラフの特徴を代数的に解析するもしくは代数的に「綺麗な」グラフを構成したり, Tutte多項式といった興味深い不変量について解析しています. ここで言う「代数」とは線形代数(スペクトラムグラフ理論)や群(Cayley graph)などです. 面白いことに正則グラフ(全ての頂点の次数がある定数に等しいグラフ)に対するゼータ関数としてIhara zeta function というものが知られていて, Ihara zeta function を用いてラマヌジャングラフと呼ばれるスペクトラムグラフ理論において非常に重要なグラフの特徴づけを与えられています.

グラフの持つ美しい性質の解析の一方で, こちらの記事で紹介したような「小直径グラフを構成する」や「彩色数と内周(girth)が共に大きいグラフ」といった, 普通のグラフでは満たされないような性質を満たすグラフをalgebraic graph theoryの道具を用いて巧妙に構成するという研究も有ります.

今回の記事では 強正則グラフ (strongly regular graph) と呼ばれるグラフについて, スペクトラムグラフ理論においてしばしば用いられるテクニック(=線形代数)を用いて解析していきます. 更にその応用として, グラフ理論における二つの未解決問題(Moore graph と Conway 99 problem)について考察してみます. あらかじめ記しておきますが, 本記事は予想以上に線形代数成分が強いです (というかグラフ理論成分は少なめです).

1. 強正則グラフ

グラフ$G$に対し, その頂点$v$に隣接する頂点の全体を$N(v)$で表します.
$n$頂点の$k$-正則グラフ$G$ (全ての頂点の次数が$k$に等しいグラフ) が以下の全ての性質を満たすとき, $G$はパラメータ$(n,k,\lambda,\mu)$を持つ強正則グラフであると言います.

1. 任意の隣接する二頂点$u,v$に対して, $|N(u)\cap N(v)|$がある定数$\lambda$に等しい.
2. 任意の隣接しない二頂点$u,v$に対して, $|N(u)\cap N(v)|$がある定数$\mu$に等しい.

イメージとしてはこんな感じです:

特に, $\mu>0$の場合はグラフの直径は$2$以下となります. $\mu=0$の場合はグラフは非連結で, 各連結成分はサイズ$\lambda+2$の完全グラフになっていて次数は$k=\lambda-1$となります.

例:

・長さ5の閉路 : $(n,k,\lambda,\mu)=(5,2,0,1)$.

・Petersen graph : $(n,k,\lambda,\mu)=(10,3,0,1)$.

Petersen graph

・$n$頂点の完全グラフ : $(n,k,\lambda,\mu)=(n,n-1,n-2,0)$.

・長さ$3$の閉路 : $(n,k,\lambda,\mu)=(3,2,1,0)$.

$\lambda$は三角形の個数, $\mu$は四角形の個数を規定している感じになっています.

2. 強正則グラフのスペクトル

$G$を$(n,k,\lambda,\mu)$をパラメータに持つ強正則グラフとします. 更に$\mu\neq 0$を仮定します. $G$の隣接行列を$A$とします. すなわち

と定めます. 今回の目的は$A$の全ての固有値を特定することです. 固有値を求めてそこから得られる様々な条件を考えることによって, 与えられたパラメータ$(n,k,\lambda,\mu)$に対応する強正則グラフの存在性について議論することが出来ます (後述).

$i\neq j$に対し, $(A^2)_{ij}$は頂点$i$から頂点$j$への長さ2のパスの本数に等しいはずです. $ij$が隣接しているときはこの値は$\lambda$と等しく, そうでないときは$\mu$に等しくなります (上図参照). $i=j$に対しては$A^2_{ij}$は次数に等しいので$k$となります. 以上より

なので, 

$A^2+(\mu-\lambda)A=(k-\mu)I+\mu J$                    ...(1)

となります. ここで $I$ は$n\times n$の単位行列, $J$は全ての要素が1に等しい$n\times n$行列です. 即ち強正則グラフの隣接行列は行列の二次方程式が成り立ちます.

$A$は$k$-正則グラフなので, 各行に含まれる$1$の個数(=次数)は全て$k$に等しいはずです. すなわち $A\mathbb{j}=k\mathbb{j}$ が成り立ちます. ここで$\mathbb{j}\in\mathbb{R}^n$は全要素が$1$の列ベクトルです. 更に$A$対称行列なので全ての固有値は実数であり, しかも最大固有値は$k$に等しく, ($\mu>0$よりグラフは連結なので, $A$は行列として既約であるため, ペロン=フロベニウスの定理より)最大固有値の多重度は$1$となります. したがって$A$の他の固有値$\theta$に対応する固有ベクトル$x$は必ず$\mathbb{j}$と直交します. このベクトル$x$を二次方程式の両辺に掛けると, ($Jx=\mathbb{j}\mathbb{j}^{T}=0$に留意して)

$(A^2+(\mu-\lambda)A)x = (\theta^2+(\mu-\lambda)\theta)x = (k-\mu)x$

となります. したがって$\theta$は以下の二次方程式:

$\theta^2+(\mu-\lambda)\theta-(k-\mu)=0$

の解になっているので, 

以上より, $A$の固有値は三種類しかなく, それらは

となることが分かりました. 更に, $A$に関する二次方程式の両辺に$\mathbb{j}$を掛けると

$k^2+(\mu-\lambda)k=k-\mu+\mu n$                    ...(2)

即ち, $k(k-\lambda-1)=(n-k-1)\mu$ が成り立ちます.

最後に, それぞれの多重度を求めてみましょう. 

とおいてそれぞれの多重度を$s,t$とおきます. すると$A$のトレース(=対角成分の和=固有値の和)は$0$に等しく, 固有値$k$の多重度は$1$であることも合わせると

$fs+gt+k=0$, $s+t=n-1$

となり, これを連立させると

                    ...(3)

が成り立ちます. 即ち $(n,k,\lambda,\mu)$をパラメータとして持つような強正則グラフが存在するためには, これら四つの値が (2)を満たしかつ(3)で与えられる$s,t$が整数とならなければいけません. これらの条件を使うことによって与えられたパラメータに対応する強連結グラフの存在性について議論することが出来ます.

先ほどみたように, 連結な強正則グラフの固有値は3種類しかありません. 面白いことに逆も成り立つことが知られています:

定理1:

$G$を連結な$k$-正則グラフで完全グラフでないものとする. $G$の隣接行列が三つの相異なる固有値$k>s>t$を持つとする. このとき, $G$は強正則グラフである.

また一般に, 固有値の種類数はグラフ(強正則でなくても良い)の直径を上から抑えるということが知られています:

定理2:

連結な$G$に対してその隣接行列が持つ相異なる固有値の個数を$m$とする. $G$の直径は$m-1$以下である.

強正則グラフは固有値は3種類しかないので直径2となっていますが, このことは定理2と整合性がとれています (余談ですが, 定理2の証明は2016年に東京大学情報理工学系研究科の数理情報学専攻の修士課程の大学院入学試験で出題されました).

応用1: Moore graph の存在性

Moore graph とは簡単に言うと「直径$D$の$d$-正則グラフの中で最も頂点を多く含んでいるグラフ」のことです. 詳しくはこちらの記事に書いてあります. Moore graphは

1. 直径$>2$の場合は存在しない
2. 直径$=2$かつ$d\not \in \{2,3,7,57\}$ の場合は存在しない.

ことが示されています. 今回は二つ目の事実をこれまでの議論を使って示していきます. こちらの記事より, 直径2のグラフ$G$が Moore graph であることの必要十分条件は, $G$が三角形と四角形を含まないことです. 更に, 明らかに$n=k^2+1$となります). 従って, $G$はパラメータ$(n,k,\lambda,\mu)=(k^2+1,k,0,1)$を持つ強正則グラフとなっていることに注意します($n=k^2+1$は今回導出した(2)の条件に$\lambda=0,\mu=1$を代入することで導出できます).

(3)の整数性条件を考えます. パラメータを代入して計算すると

即ち, $k^2-2k=0$ もしくは $4k-3=p^2$ ($p\in\mathbb{N}$) が必要条件となります. $k^2-2k=0$, 即ち$k=2$に対しては長さ$5$の閉路が対応しています. ２番目の条件より, $k=(p^2+3)/4$ を $s$ に代入すると,

$s=\frac{p^4+6p^2+9}{32}+\frac{p^4-2p^2-15}{32p} = \frac{p^5+p^4+6p^3-2p^2+9p-15}{32p}$

整理すると

$p^5+p^4+6p^3-2p^2+(9-32s)p=15$

従って$p$は$15$を割り切るので, $p\in \{1,3,5,15\}$となり, それぞれの$p$を$4k-3=p^2$に代入ことにより, $k=1,3,7,57$ が得られます. $k=1$の時は$n=k^2+1=2$より, グラフは$K_2$となります (直径2ではないのでこれは除外します).

従って, 直径2のMoore graphが存在するならば, $k\in \{2,3,7,57\}$ が成り立ちます.

応用2: Conway 99 graph problem

元ネタ : https://oeis.org/A248380/a248380.pdf
関連文献 : https://arxiv.org/abs/1707.08047

こちらの問題はグラフ理論というよりは, Conwayが出した未解決な問題であり, 解けたら1000ドルもらえるというプチミレニアム未解決問題です. 具体的には次のような問題です:

問題: 以下の二つの性質を満たす$99$頂点のグラフは存在するか否か.

1. 任意の隣接している二頂点$u,v$に対して, $u,v$を含む三角形が唯一存在する.
2. 任意の隣接していない二頂点$u,v$に対して, $u,v$を対角線上に含むような四角形が唯一存在する.

イメージとしては次のような感じです:

三角形は被ってはいけない. 四角形は二辺を共有してはいけない.

本記事では条件1を三角形条件, 条件2を四角形条件と呼ぶことにします (番号が乱立して可読性が下がるため)

問題を見た感じだと正則グラフには見えないのですが, もし所望のグラフ$G$が存在するとして, それが$k$-正則であったならば, $G$はパラメータ$(99,k,1,1)$を持つ強正則グラフであることが分かります. すると(2)の条件より, $k=14$が出てきます. そもそもなぜ頂点数が99なのでしょうか？この記事ではより一般に, パラメータ$(n,k,1,1)$を持つ強正則グラフについて考え, どのような$n$と$k$に対してそのグラフが存在するのかについて考えていきます.  まず明らかですが, $n=3,k=2$に対しては$K_3$が所望の性質を満たすことが確認できます(非隣接点が存在しないため). これ以外に所望のグラフはあるのでしょうか？

実は, 所望のグラフが存在するとしたら, そのグラフは必ず正則であることが次のようにして証明できます:

$G=(V,E)$の頂点数を$n$とします. $G$において隣接している二頂点$u,v$を任意にとってきます. するとある頂点$w\in V\backslash \{u,v\}$が一意に存在して$uvw$が三角形となります. 更に$n\geq 4$のとき, $G$の直径は$2$であり, $k\geq 3$となる ($k=2$ならば$n=3$となってしまうから). 従って$u$に隣接する頂点$z\in V\backslash \{v,w\}$が存在し, この$z$はどれも$v$には隣接していない (そうでないならば, $uvz$が三角形条件に反する. 下図1参照).

図1 : $z$と$v$は隣接してはいけない.

　そこで$z, v$に対して四角形条件を適用すると, $zv$を対角線として持つような四角形$uvz'z$が存在することになります. 特にこの四角形は一意なので, $z$に対して$z'$は唯一定まります (図2). 特に$z'\in N(v)$に注意します.

図2. $vz$を対角線に持つような四角形がとれる. 一方で$z$に対して複数の$z'$をとることは出来ない.

そこで写像$z\mapsto z'\in N(v)$を考えると, これは単射になっています. $z_1\neq z_2 \in N(u)$に対して$z_1\mapsto z'$, $z_2\mapsto z'$となると四角形条件に反するからです.

図3: $z_1,z_2 \mapsto z'$となると$uz'$を対角線に持つ四角形が二つできてしまう.

従って, 単射$N(u)\to N(v)$が構成できた(実際は全単射になっている)ので, $|N(u)|\leq |N(v)|$. 同様にして逆も言えるので, $|N(u)|=|N(v)|$. $G$は連結なので, どの頂点の次数もある定数に等しい. よって$G$は正則である.

以上より, 議論すべきグラフは正則なので, パラメータ$(n,k,1,1)$を持つ強正則グラフです. 更に(2)の条件より, $n=\frac{k^2}{2}+1$となります. $n$の整数性から$k$が偶数であることも直ちに従います. さらに, 固有値の多重度の整数性条件から





すなわち$k^2-4k=0$, $4k-7=p^2$となります.

$k^2-4k=k(k-4)=0$の場合は$k=4$となり, 対応する$n$は$n=\frac{k^2}{2}+1=9$.

$4k-7=p^2$の場合は$k=(p^2+7)/4$を$s$に代入することにより





従って, $p^5+p^4+14p^3-2p^2+(49-64s)p=63$ となるので, $p$は$63$を割り切ります. 即ち$p\in \{1,3,7,9,21,63\}$. 対応する次数$k$は$k\in\{2,4,14,22,112,994\}$.

まとめると, $(n,k,1,1)$をパラメータとして持つ強正則グラフが存在するための十分条件は(計算ミスがなければ)





実際, $(n,k)=(3,2)$に対しては$C_3$が対応しています. しかし$(n,k)=(9,4)$に対しては存在しないことが示せます(三角形条件と四角形条件を使って局所的な構造を絞ることによって示せますがあまり証明としては綺麗ではありません). こちらにあるように, $(n,k)=(9,4)$は具体的にグラフが構成でき, 隣の研究室の後輩に教えられたのですが, $K_{3,3}$の線グラフ(辺と頂点を交換したグラフ)が条件を満たしています. (2018年7月24日追記) $(n,k)=(99,4)$はConwayの99問題に対応しています. 他にも三つほどヤバそうな$(n,k)$がありますが, とりあえず有限個であることは以上の議論より示すことが出来ました.

要するに「99」という数字の本質は線形代数的な議論によって導かれます. また, Moore graphにおいても「次数57」の条件は同様な議論から導出できます. 即ち「良い性質を持った」グラフの存在性については未だに線形代数的な議論によってしか条件を絞り込むことが出来ていないというのが現状です. 従って今回提示した二つの未解決問題を解くためには, 線形代数から少し離れたアプローチ, もしくはよりグラフ理論っぽいアプローチから新たな必要条件を導出するしかないんじゃないかなぁとなんとなく思っています.

3. まとめ

今回の記事では「スペクトラムグラフ理論」と言いながらほとんど「スペクトラムグラフ」感が感じられないものだったので, あまりその凄さが通じなかったのかもしれません. しかし実はスペクトラムグラフ理論の技法はグラフの構造上の特徴の情報を得ることが出来ます. 例えば, $(n,k,1,1)=(99,14,1,1)$をパラメータに持つ強正則グラフ(Conwayの問題におけるグラフ)が存在するならば, その最大独立点集合のサイズが高々22であり, 彩色数は5以上である, ということを証明することが出来ます (驚くべき証明があるのですが余白がないので省略します).

そして実際に今回示した手法によってMoore graph や Conway problem に対してある程度までの必要条件を導出することが出来ました. なお今回のConway problemに関する結果については僕は論文でも見たことはなく, (載っている論文がぱっと見見つからないという意味で)新しいものなのかもしれませんが, 教科書に載っている程度の初等的な議論によって得られる結果なので「プロ」の研究者にとっては既知の情報かとは思います. また, 今回の議論は次を参考文献として提示します.

• "Elementary Number Theory, Group Theory and Ramanujan Graphs", Giuliana Davidoff, Mount Holyoke College, Massachusetts Peter Sarnak, (2003)

こちらの本はグラフスペクトル理論の初歩的な部分について解説していて, Ramanujan graph についての話題が書いてあります. 前提知識もあまり必要でなく, 非常に読みやすかったです.

• "Topics in Graph Automorphisms and Reconstruction", Josef Lauri, University of Malta Raffaele Scapellato, Politecnico di Milano, (2016)

こちらの本は algebraic graph theory に関わる話題として automorphism (vertex-transitivityなど)や, グラフ理論における非常に有名な未解決問題: reconstruction conjecture について紹介しています. strongly regular graph, Moore graphについて節が割かれています.

高速な全点対最短経路アルゴリズム

1. 全点対最短経路問題の計算量の外観

　グラフ $G$ が与えられたときに全点対最短経路(APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと思います. しかしこれらのアルゴリズムは頂点数 $n$ に対して最悪 $O(n^3)$ 時間かかってしまうので, $n=1000$くらいでもちょっと厳しい感じがあります.

　実は辺重み付きグラフのAPSPの計算量には多くの歴史があり、ワーシャルフロイド法以降様々なアルゴリズムが提案されてきました.

APSPのアルゴリズムの歴史

　しかし、任意の $\epsilon>0$ に対して $O(n^{3-\epsilon})$ 時間でAPSPを解くアルゴリズムはこれまで知られていません. なので現在ではそのようなアルゴリズムは存在しないのではないかと予想されています. ちなみにSETHの仮定の下で計算量の下界が示されている問題が多くありますが, APSPのこの下界をSETHの仮定の下で示すのは難しいだろう, という根拠が2016年にCarmosino, Gao, Impagliazzoらによって示されました.

2. 重み無しグラフの全点対最短経路

　以上のことから, 辺重み付きグラフのAPSPを$O(n^{2.99})$で解くのは絶望的であると言えます. では, 辺重み無しグラフのAPSPについてはどうなのでしょうか？以降は「グラフ」は辺重み無しグラフを指すこととします.

　頂点数$n$, 辺数$m$のグラフのAPSPは各頂点から幅優先探索を行うことによって $O(nm)$ 時間で解くことができます. したがってグラフが密で, $m=\Omega(n^2)$ であるならば計算時間は $O(n^3)$ だけかかってしまいます. 

　結論から言うと辺重み無しグラフのAPSPは$m$に依存せず $O(n^{\omega}\log n)$ 時間で解くアルゴリズムが存在します. そのアルゴリズムは[Seidel, 1992]で初めて与えられました. 非常にシンプルなので, 本記事ではこのアルゴリズムについて解説します.

3. Seidel のアルゴリズム

　前提として入力として与えられるグラフ$G$は連結であるとします. したがってその直径は高々$n$です. 更に, 入力において$G$は隣接行列として与えられるとします. そしてアルゴリズムの出力は距離行列$D$とします. ただし$D_{ij}=ij$間の最短経路長と定義します.

　グラフ $G$ に対し, 任意の辺$uv,vw \in E(G)$ に対して 新たな辺$uw$を$G$に追加して得られるグラフを$\tilde{G}$ と定めます. 気持ちとしては$\tilde{G}$ は「全ての長さ2のパスに対してその端点を結ぶ」ことを出来るだけ行って得られるグラフです.

追加した辺を赤く塗っています. 三角形がめちゃくちゃ増えます.

$A$を$G$の隣接行列とします. すると$\tilde{G}$の隣接行列$\tilde{A}$は

になります ($i\neq j$に対し$A^2$の$ij$成分は$ij$間の長さ2のパスの本数を表すからです). したがって, $A^2$を$O(n^{\omega})$時間で計算することで$\tilde{A}$が計算できるので, $\tilde{G}$を得ることが出来ます. 

　この$\tilde{G}$に対して再帰によってAPSPの距離行列$\tilde{D}$を得ます. $\tilde{G}$の直径は$G$の直径の半分くらいになっているので, 再帰を繰り返した結果, 最終的には$G$の直径が$1$(=完全グラフ)となり, この時は(再帰のベーシックケースとして)出力$D$は非対角成分が全て1の行列となります. 更に, 再帰の深さは$\log n$くらいです. というのも$G$の直径が高々$n$で, 一回の再帰で直径が半分くらいになるからです.

　さて, 再帰の出力$\tilde{D}$を使って$G$の距離行列$D$を得ましょう. 下図のように, $\tilde{G}$の$ij$間の最短経路を考えます. 明らかに, 元のグラフ$G$における$ij$間の最短経路長$d_{ij}$が奇数であれば, $\tilde{G}$における$ij$間の最短経路長$\tilde{d}_{ij}$に対して $d_{ij} = 2\tilde{d}_{ij}-1$ が成り立ちます (下図(a)参照. $\tilde{G}$では長さ2のパスを1ホップで通過出来るので, 出来るだけ新しい辺を利用した方が経路長が短くなる). 一方で$\tilde{d}_{ij}$が偶数であれば, $d_{ij}=2\tilde{d}_{ij}$が成り立ちます (下図(b)). 以上より, $d_{ij}$のパリティが分かれば$\tilde{d}_{ij}$を用いて$d_{ij}$を復元できます.

元の最短経路長のパリティが分かれば復元できる.

　ここで, $\tilde{G}$上で ① $ij$間に(a)の図のような最短経路が存在する場合, $d_{ij}=2\tilde{d}_{ij}-1$となります. 一方で ② そのような最短経路が存在しない場合(つまり任意の$ij$間の最短経路が(b)のように赤い辺のみで構成されている場合), $d_{ij}=2\tilde{d}_{ij}$となることに注意します. つまり$d_{ij}$を復元するためには①と②の場合を判別する必要があります.

　そのために行列$X:=\tilde{D}A$を考えます. これは行列積なので$O(n^{\omega})$時間で計算できます. 行列積の定義より$X_{ij}$は

$X_{ij}=\sum_{k=1}^n \tilde{d}_{ik}\cdot A_{kj} = \sum_{k \in N(j)} \tilde{d}_{ik}$

となります. ここで$N(k)$は$G$における$k$の隣接点の集合, $\tilde{d}_{ik}$は$\tilde{G}$における$ik$間の最短経路長です. 

　②を仮定します. すると任意の$k\in N(j)$に対し, $\tilde{d}_{ik} \geq \tilde{d}_{ij}$ が成り立ちます (そうでないとすると, $\tilde{G}$上の$ik$間の最短経路に辺$kj$を足したものが$ij$間の最短経路になりますが, それは②に反するからです. 下図参照).

②で考えるケース. どの$k\in N(j)$も$\tilde{G}$上の$ij$間の最短経路上に含まれていない.

したがって

$\sum_{k \in N(j)} \tilde{d}_{ik} \geq \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

となります. ここで$\mathrm{deg}(j)=|N(j)|$は頂点$j$の$G$における次数です.

　次に①について考えます. この時はある$k\in N(j)$に対して$k$を含むような$\tilde{G}$上の$ij$間最短経路が存在します (下図).

　この$k$に対して $\tilde{d}_{ik} = \tilde{d}_{ij}-1$ が成り立ちます. 更に他の$k'\in N(j)$ に対しても $\tilde{d}_{ik'} \leq \tilde{d}_{ik}+1 = \tilde{d}_{ij}$が成り立ちます ($k$と$k'$間は$\tilde{G}$の辺で繋がっています. 下図参照).

したがって

$\sum_{k \in N(j)} \tilde{d}_{ik} < \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

が成り立ちます.

以上より, 

① $\iff$ $X_{ij}=\sum_{k \in N(j)} \tilde{d}_{ik} < \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

② $\iff$ $X_{ij}=\sum_{k \in N(j)} \tilde{d}_{ik} \geq \tilde{d}_{ij}\cdot \mathrm{deg}(j)$.

が成り立つので, 

として$d_{ij}$を求めることが出来ます. これでめでたく出力すべき$D=(d_{ij})$を構成することが出来ました.

　アルゴリズム全体の流れとしては

1. $G$の直径が$1$ならば自明な解を出力.
2. そうでないときは, $A^2$を計算することで$\tilde{A}$を計算し, 再帰に投げることで$\tilde{D}$を得る.
3. $X=\tilde{D}A$を計算し, $X$と$\tilde{D}$を用いて各$ij$に対して$d_{ij}$を計算する.
4. $D=(d_{ij})$を出力.

という感じになります. まず再帰の深さは$O(\log n)$で, ステップ2, 3においては行列積を計算しているので計算時間は$O(n^{\omega})$となり, ステップ4では$O(n^2)$かかるので, 全体の計算時間は$O(n^{\omega}\log n)$となります.

4. まとめ

　辺に重みがある場合と無い場合でAPSPの計算量には大きなギャップがあります. 辺重み付きグラフでは$O(n^{2.99})$では解けなさそうである一方, そうでないグラフに対しては$O(n^{\omega}\log n)=O(n^{2.38})$時間で解くアルゴリズムが知られています. もちろん辺重みが無いスパースなグラフに対しては依然として幅優先探索を用いた$O(nm)$の方が高速ですが, 密な場合はSeidel のアルゴリズムの方が高速であると言えます.
　では, 重み付きグラフに対して$O(n^{2.99})$時間でAPSPを計算するアルゴリズムは存在するのでしょうか？これは$P\neq NP$ほどではないですが, 計算量理論においてかなりホットな話題なので, みなさんもぜひ挑戦してみてください.

問題を解きやすいグラフクラスとその拡張

NP-困難な問題はP≠NPの仮定のもとでは多項式時間で解けません. しかしNP-困難な問題を解きたいという場面が少なからずあります. そのようなときには近似を考えたり入力インスタンスのクラスを制限する、ということを考えることが多々あります.

今回のトピックはグラフに対する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 ではありません. このことから定理の片方の向き (右から左) が言えます.