単純無向グラフ $G = (V, E)$ に対し、頂点と辺の個数を $n, m$ 、平均次数を $\Delta$ で表します。 このとき、グラフ $G$ にはサイズ $\Omega(n / \Delta)$ の独立集合が存在します。 そして、そのような独立集合を線形時間、すなわち $O(n + m)$ 時間で計算できます。 今回はそのアルゴリズムを紹介します。
用語の定義
- 平均次数
頂点 $v$ に対して「$v$ を端点に持つ辺の個数」を $v$ の次数と呼び、 $\mathrm{deg}(v)$ で表します。 平均次数とはその平均、すなわち、以下の値です。 $$ \Delta = \frac{\sum_{v \in V} \mathrm{deg}(v)}{n}. $$
- 独立集合
独立集合とは、頂点集合 $I \subseteq V$ であって、隣接する2点を含まないものです。 すなわち、 $I$ に含まれる任意の2頂点 $u, v$ について、辺 $\{u, v\} \not\in E$ であるものです。
線形時間アルゴリズム
以下のアルゴリズムは、サイズ $\Omega(n / \Delta)$ の独立集合を出力します。
- $S$ を空集合とする。
- 次数が $2\Delta$ 以下の頂点すべての集合を $Q$ とする。
- $Q$ が空になるまで、以下を繰り返す。
- $Q$ から任意に頂点 $v$ を一つ削除し、 $S$ へ加える。
- $Q$ から $v$ に隣接する頂点すべてを削除する。
- $S$ を出力する。
線形時間で動作するか？
データの持ち方に少し工夫が必要です。 $S, Q$ それぞれ、「頂点 $v$ が属するか？」のビット値の配列で表現します。 以下の部分では、 $Q$ を表現する配列の先頭から順に見ていき、 $Q$ に属する頂点を見つけるごとにその頂点を $v$ として処理していけばよいです。
- $Q$ が空になるまで、以下を繰り返す。
- $Q$ から任意に頂点 $v$ を一つ削除し、 $S$ へ加える。
- $Q$ から $v$ に隣接する頂点すべてを削除する。
正当性の証明
上記のアルゴリズムが独立集合を出力することはあきらかです。 したがって、出力する $S$ のサイズが $\Omega(n / \Delta)$ であることを示します。
まず、 $Q$ のサイズが $\lceil n / 2 \rceil$ 以上であることを背理法で示します。
証明： 次数が $2\Delta$ より大きい頂点が $\lceil n / 2 \rceil$ 個あると仮定します。 このとき、以下のとおり矛盾が生じます。 $$ \Delta = \frac{\sum_{v \in V} \mathrm{deg}(v)}{n} \geq \frac{(2\Delta + 1) \cdot \lceil n / 2 \rceil}{n} \geq \frac{(\Delta + 1/2) \cdot n}{n} > \Delta. $$
一方で、 $v \in Q$ について、「 $v$ とその隣接頂点」の個数は高々 $2 \Delta + 1$ 個です。 すなわち、アルゴリズムの3の各ループでは高々 $2 \Delta + 1$ 個の頂点しか $Q$ から削除されません。 したがってアルゴリズムの3は少なくとも $\lceil n / 2 \rceil / (2 \Delta + 1) = \Omega(n / \Delta)$ 回繰り返され、 $S$ のサイズも $\Omega(n / \Delta)$ です。