次数分離: スパースなグラフで役立つアルゴリズムのアイデア

単純無向グラフ$G=(V,E)$上で長さ$k$の閉路を探したり直径を求めたくなったりする時があります。そして時には$G$はスパースになっていることを利用したくなります。今回の記事では、スパース性を利用した単純ながら面白く賢いトリック (次数分割: high-degree low-degree technique)を紹介し、これに基づいてグラフに含まれる三角形 (長さ3の閉路) の個数の数え上げを行う非自明なアルゴリズムを紹介します。次数分離という和名は私が勝手に名付けたものであり世間で浸透しているものではないので注意してください (もし世間で浸透している名前をご存知の方がいらっしゃいましたら教えていただけると嬉しいです...!!）。このアイデアはAlon, Yuster, Zwick [1] によるものです。

$|E|=m$, $|V|=n$とします。一般には$m=O(n^2)$になりえますが、今回は$G$がスパースであることを仮定してるので$m=O(n)$を想定します。ただ次数分離は一般の$m$に対しても適用でき、例えば$m=O(n^{1.5})$とかでも似たような解析で計算時間を見積もることができます。

次数分割の基本アイデア

頂点$v$の次数を$\deg(v)$とします。$\alpha\in[0,1]$をパラメータとし、

$$H=\{v\in V: \deg(v)>n^\alpha\},$$

$$L=V\setminus H$$

とします ($H$は high degree、$L$は low degree のイメージです）。すると、$2m=\sum_v \deg(v)$ なので

$$2m \geq \sum_{v\in H} \deg(v) > |H|n^\alpha$$

より$|H|<2m/n^\alpha$となります。特に$m=O(n)$ならば$|H|=O(n^{1-\alpha})$となり、$n$と比べて小さくなります。これらの頂点部分集合は$O(m)$時間で得られます (計算モデルは$O(\log n)$bit-Word-RAM モデルを仮定)。

応用. 三角形(長さ3の閉路$C_3$)の数え上げ

入力としてグラフ$G=(V,E)$が与えられ、$G$に含まれる長さ$3$の閉路$C_3$と同型な部分グラフを数え上げる問題を解いてみましょう。以下の二つの素朴なアルゴリズムを考えます。

・アルゴリズム1:

$G$の隣接行列の三乗を計算し対角成分の総和を見ると、長さ3の閉じたウォークの個数となり、これは三角形の個数の$3!=6$倍になっています。従って$O(n^{\omega})$時間で数え上げられます。 ($\omega<2.373$は高速行列積の指数)。

・アルゴリズム2:

各頂点に対して隣接点を列挙して隣接点のペアで隣接しているものがあるかどうかを見れば$O(\sum_{v\in V}\deg(v)^2)$時間で数え上げが解けます。$(2m)^2=\left(\sum_{v\in V}\deg(v)\right)^2\geq \sum_{v\in V}\deg(v)^2$より、このアルゴリズム2は$O(m^2)$時間なので、例えば$m=O(n)$なら$O(n^2)$となりアルゴリズム1以上に高速になります ($\omega=2$なら同等のオーダーになる)。

ここで、冒頭に説明したアイデアを考えます。適当なパラメータ$\alpha\in[0,1]$に対して上で定義した頂点部分集合$H,L$を得ます。入力グラフ$G$に含まれる三角形$C_3$は以下の二つのケースに分類されます:

ケース1. 三頂点全てが$H$に含まれる場合

ケース2. 一つ以上の頂点が$L$に含まれる場合

ケース1は誘導部分グラフ$G[H]$内に含まれる三角形の個数を数え上げれば良く, $|H|=O(n^{1-\alpha})$より素朴なアルゴリズム1を用いれば$O(n^{\omega(1-\alpha)})$時間で数え上げることができます。

ケース2は$L$に含まれる全ての頂点に対し素朴なアルゴリズム2を用いることで列挙できるので、数え上げることができます。このとき、$k$頂点が$L$に含まれるような三角形 $(k=2,3)$ は$k$回列挙されるため適当な値で割ったりする必要があるので気をつけてください。列挙にかかる時間は、$L$に属する頂点の次数が高々$n^\alpha$であるので $\sum_{v\in L}\deg(v)^2 \leq n^{1+2\alpha}$ となります。

以上より、$m=O(n)$の場合は任意の$\alpha\in[0,1]$に対して三角形の数え上げを

$$O(n^{\omega(1-\alpha)}+n^{1+2\alpha})$$

時間で解くことができます。$\alpha=\frac{\omega-1}{\omega+2}$とおくとこの計算時間は$O(n^{3-\frac{6}{\omega+2}})$時間になります。現状では$\omega<2.373$なのでこの計算時間は$O(n^{1.628})$となり, $O(n^2)$よりも高速になっています。もし将来$\omega=2$になることがあれば$O(n^{1.5})$となります。

上の解析では$m=O(n)$を仮定していましたが一般の$m$に対しても同様の解析で$O(m^{3-\frac{6}{\omega+2}})$時間で計算できることを示せます ($|H|=O(m^{1-\alpha})$となるので)。

まとめ

スパースなグラフに対して、ある閾値を設定しそれより高い次数を持つ頂点集合とそれ以外の頂点集合に分割するテクニックを紹介し、その応用として三角形の数え上げ問題を取り上げました。本質的には、このような分離を行い、低次数の頂点の探索は近傍を見るコストが低いことを利用し、高次数の頂点の探索はまとめて処理できる賢いアルゴリズムを利用する、というだけのことです。

三角形と同様の解析を用いれば、例えば入力グラフが四角形(長さ4の閉路)を部分グラフとして持つかどうかの判定問題を$O(m^{4/3})$時間で組合せ的 (高速行列積という飛び道具を使わず初等的に）解くことができます。$H$と$L$に分解したあと、$H$内部の四角形を鳩の巣原理に基づくアルゴリズム (昔の記事参照) で判定し、$L$の頂点を含む四角形は近傍探索を駆使して判定します。結構実装も簡単でシンプルかつ汎用性がありそうなアイデアなので、競技プログラミングで出ても良さそうな気が個人的にはします（というか既にある？？）

参考文献

[1] N. Alon, R. Yuster, and U. Zwick, Finding and counting given length cycles, Algorithmica, 1997.