誘導部分グラフの数え上げ問題

注意

グラフは全て単純無向グラフとする。
グラフ $G$ の頂点数を $N$ 、辺数を $M$ と表す。
頂点 $i$ の次数を $d _ i$ と表す。
グラフの隣接行列の成分を $A _ {i ,j}$ と表す。

概要

以下の問題を考える。

$N$ 頂点 $M$ 辺のグラフ $G$ が与えられる。 $G$ に部分グラフとして含まれる $C _ 3$ の個数と $G$ の補グラフ $\overline{G}$ に部分グラフとして含まれる $C _ 3$ の個数の和を求めよ。

この問題は、以下のような考察により $O(N+M)$ 時間で解くことができることが知られている。

相異なる頂点の組 $(i,j,k)$ であって、以下の条件を満たすものを考える。

$G$ において、 $i, j$ 間に辺が存在し、 $i, k$ 間に辺が存在しない。

このような組の個数は、 $i$ を固定することで簡単に数えられる。具体的には、個数は $\sum _ {i=1} ^ n d _ i (n - 1 - d _ i)$ と表される。
相異なる $3$ 頂点の集合 $\{i, j, k\}$ について、 $\{i, j, k\}$ による $G$ の誘導部分グラフまたは $\overline{G}$ の誘導部分グラフが $C _ 3$ となる場合、個数に $0$ の寄与があり、そうでない場合、個数に $2$ の寄与がある。
よって、求める個数は
$\binom{N}{3} - \frac{1}{2} \sum _ {i=1}^N d _ i (N - 1 - d _ i)$ である。

$G$ に含まれる $C _ 3$ の個数を数える通常のアルゴリズムは $O(M \sqrt{M})$ 時間であり、 $O(N+M)$ 時間で簡単に解けるアルゴリズムは知られていない。にもかかわらず、補グラフとの個数の和は簡単に計算できるところが興味深い。本記事では、より一般に、グラフに含まれる特定の誘導部分グラフの個数を数え上げる問題の構造を分析し、このような現象が生じる理由を説明する。

誘導部分グラフ数え上げ問題

グラフ $G, H$ に対し、グラフ $G$ の相異なる $|V(H)|$ 個の頂点の組 $(v _ 1, v _ 2, \dots, v _ {|V(H)|})$ であって、それらの頂点による $G$ の誘導部分グラフが $H$ に同型であるものの個数を $count _ H(G)$ と書く。

グラフを引数とする実数値関数 $f$ が以下の条件を満たすとき、 $f$ は 誘導部分グラフ数え上げ関数 であるという。

あるグラフ $H _ 1, H _ 2, \dots, H _ k$ と実数 $c _ 1, c _ 2, \dots, c _ k$ が存在し、任意のグラフ $G$ について $f(G) = \sum _ {i=1} ^ k c _ i \cdot count _ {H _ i} (G)$ と表される。

さらに、 $H _ i$ がすべて $n$ 頂点のグラフであるとき、 $f$ は $n$ 頂点誘導部分グラフ数え上げ関数 であるという。

すべての誘導部分グラフ数え上げ関数の集合を $V$ とおき、その部分集合である、 $n$ 頂点誘導部分グラフ数え上げ関数の集合を $V _ n$ とおく。 $V$ および $V _ n$ は、実数値関数に関する自然な加法とスカラー倍について $\mathbb{R}$ 上のベクトル空間をなす。 $n$ 頂点のグラフが同型を除いて $H _ 1, \dots, H _ {a _ n}$ の $a _ n$ 個であるとき、 $count _ {H _ i} (H _ j) = \delta _ {i,j}$ であるから、 $V _ n$ は $(count _ {H _ i}) _ i$ を基底とする $a _ n$ 次元ベクトル空間となる。

さらに、任意の関数 $F(N,M)$ について、 $O(F(N,M))$ 時間で計算できる誘導部分グラフ数え上げ関数の集合は $V$ の部分空間をなす。なぜならば、いくつかの関数 $f _ 1, \dots, f _ k$ がそれぞれ $O(F(N,M))$ 時間で計算できるならば、それらの線形結合も $O(F(N,M))$ 時間で計算できるからである。

$3$ 頂点の場合

$O(N+M)$ 時間で計算できる誘導部分グラフ数え上げ関数のなす $V _ 3$ の部分空間を $W$ とおく。 $W$ を特定することが目標である。

$3$ 頂点のグラフは同型を除いて $4$ つである。辺が $0, 1, 2, 3$ 本であるものをそれぞれ $H _ 1, H _ 2, H _ 3, H _ 4$ とおく。 $V _ 3$ の元を、基底 $(count _ {H _ i}) _ i$ による成分表示で $\mathbb{R} ^ 4$ の元と同一視する。

以下、 $\sum _ {i,j,k}$ と書いたら、暗黙に $i, j, k$ は相異なることを課すとする。

$(c_1, c_2, c_3, c_4) \in \mathbb{R}^4$ とし、 $f(n)$ を $f(n) = c _ {n+1} \, (n = 0,1,2,3)$ なる関数とすると、 $\sum _ {i, j, k} f(A _ {i,j} + A _ {j,k} + A _ {k,i})$ は $V _ 3$ に属し、その成分表示は $(c _ 1, c _ 2, c _ 3, c _ 4)$ である。

$f(n) = 1$ とおくと、 $\sum _ {i, j, k} f(A _ {i,j} + A _ {j,k} + A _ {k,i}) = N(N-1)(N-2)$ である。よって、 $N(N-1)(N-2) \in W$ で、その成分表示は $(1, 1, 1, 1)$ である。

$f(n) = n$ とおくと、 $i, j, k$ の対称性に注意し、 $\sum _ {i, j, k} f(A _ {i,j} + A _ {j,k} + A _ {k,i}) = 3 \sum _ {i, j, k} A _ {i,j} = 6M(N-2)$ である。よって、 $6M(N-2) \in W$ で、その成分表示は $(0, 1, 2, 3)$ である。

$f(n) = n^2$ とおくと、 $i, j, k$ の対称性に注意し、 $\sum _ {i, j, k} f(A _ {i,j} + A _ {j,k} + A _ {k,i}) = 3 \sum _ {i, j, k} A _ {i,j}^2 + 6 \sum _ {i, j, k} A _ {i,j} A _ {i,k} = 6M(N-2) + \sum _ {i=1} ^ N d _ i (d _ i - 1)$ である。よって、 $6M(N-2) + 6\sum _ {i=1} ^ N d _ i (d _ i - 1) \in W$ で、その成分表示は $(0, 1, 4, 9)$ である。 $6M(N-2)$ を引き $2$ で割ると、 $3\sum _ {i=1} ^ N d _ i (d _ i - 1) \in W$ で、その成分表示は $(0, 0, 1, 3)$ である。

$(1,1,1,1), (0,1,2,3), (0,0,1,3)$ は $1$ 次独立であるから、 $W$ は少なくとも $3$ 次元である。

グラフに含まれる $C _ 3$ を数え上げる問題、すなわち関数 $(1,0,0,0)$ を計算する問題が $O(N+M)$ 時間で解けないと仮定する。このとき、 $W \subsetneq V _ 3$ であるから、 $\dim W < \dim V _ 3 = 4$ である。よって、 $W$ は $(1,1,1,1), (0,1,2,3), (0,0,1,3)$ により張られる部分空間に一致する。これは、 $W = \{(c _ 1, c _ 2, c _ 3, c _ 4) \mid c _ 1 - 3 c _ 2 + 3 c _ 3 - c _ 4 = 0\}$ とも表される。

例 1

本記事冒頭の問題を解く方法を導出する。 $3$ 頂点に順序をつけて考え、最後に $6$ で割ればよい。 $(1, 0, 0, 1)$ は $1 - 3 \cdot 0 + 3 \cdot 0 - 1 = 0$ を満たすので、 $W$ の元である。よって、 $(1,0,0,1)$ は $O(N+M)$ で計算できる。

$(1,0,0,1)$ を $W$ の基底 $(1,1,1,1), (0,1,2,3), (0,0,1,3)$ の線形結合で表すと、 $(1,0,0,1) = (1,1,1,1) - (0,1,2,3) + (0,0,1,3)$ となる。よって、 $(1,0,0,1)$ を計算する計算式は $N(N-1)(N-2) - 6M(N-2) + 3 \sum _ {i=1} ^ N d _ i (d _ i - 1)$ である。これは確かに冒頭で求めた式の $6$ 倍と一致する。

例 2

以下の問題を考える。

相異なる頂点 $i, j, k$ であって、 $\{i, j, k\}$ により誘導される誘導部分グラフがちょうど $2$ 本の辺を持つものの個数を求めよ。

$(0, 0, 1, 0)$ を計算すればよい。 $1 \cdot 0 - 3 \cdot 0 + 3 \cdot 1 - 0 \cdot 0 = 3 \neq 0$ より、 $(0,0,1,0) \notin W$ である。よって、(上の仮定の下で) この問題は $O(N+M)$ 時間で解くことができず、 $C _ 3$ の数え上げアルゴリズムが必要である。

$(1,1,1,1), (0,1,2,3), (0,0,1,3), (1,0,0,0)$ は $V _ 3$ の基底をなす。 $(0,0,1,0)$ をこれらの線形結合で表すと、 $(0,0,1,0) = -3(1,1,1,1)+3(0,1,2,3)-2(0,0,1,3)+3(1,0,0,0)$ となる。よって、 $(0,0,1,0)$ を計算する計算式は $-3N(N-1)(N-2) + 3 \cdot 6M(N-2) - 2 \cdot 3\sum _ i d _ i (d _ i - 1) + 3count _ {C _ 3} G$ であり、 $O(M\sqrt{M})$ 時間で計算できる。