この記事は 木 Advent Calendar 2025 の 21 日目です。

概要

グラフ $G$ に対して、その木幅を $\mathrm{tw}(G)$ で表記します。

この記事では、以下の判定問題を解くシンプルなアルゴリズムを紹介します。

入力: $n$ 頂点 $m$ 辺の（単純無向）グラフ $G = (V, E)$
出力: $\mathrm{tw}(G) \leq 3$ か？

詳しい方は、これらの事実をご存知かもしれません。

  • そもそも任意の $k$ について木幅が $k$ 以下かの判定が $O(f(k) \cdot n)$ 時間で解ける (☆)
  • 有限個の木幅 $3$ 以下の禁止マイナーを確認すれば $O(n^{1+o(1)})$ 時間で解ける (☆) (★)

今回紹介するアルゴリズムはそういった強そうなものではなく、グラフが与えられたときに紙とペンで簡単に木幅が $3$ 以下か判定できる、人間にもやさしいアルゴリズムです。 [Arnborg & Proskurowski, 1986] によるアルゴリズムです。

この記事の内容はニッチなので、多少木幅に親しい読者を仮定しています。 木幅・木分解に触れたことがない場合、岡本先生の資料をおすすめします。

準備

木幅・木分解

グラフ $G = (V, E)$ の木分解 $\mathcal{T}$ は、木 $T$ と頂点集合族 $\mathcal{X} = \{X_t \subseteq V \mid t \in V(T) \}$ の組であって、以下の条件をすべて満たすものです。

  • $\bigcup_{t \in V(T)} X_t = V$ である。
  • 任意の辺 $\{u, v\} \in E$ について、ある $t \in V(T)$ が存在し、 $\{u, v\} \subseteq X_t$ である。
  • 任意の頂点 $u \in V$ について、頂点集合 $V_u = \{t \in V(T) \mid u \in X_t\}$ は $T$ 上で連結である。すなわち、誘導部分グラフ $T[V_u]$ が連結である。

（インフォーマルですが）この記事では木 $T$ の各頂点 $t$ をバッグと呼び、 $X_t$ がその中身、のような表現をします。

木分解 $\mathcal{T}$ の幅は、バッグのサイズの最大値 $\max\{|X_t| \mid t \in V(T) \} - 1$ として定義され、グラフ $G$ の木幅 $\mathrm{tw}(G)$ は任意の木分解の幅の最小値です。

木幅・木分解の重要な性質

任意のグラフ $G$ について、これらが知られています。 folklore なので、証明は検索したら出てくると思います。

性質 1
グラフ $G$ の木幅は連結成分の木幅の最大値に一致する。 つまり、 $G$ の連結成分を $C_1, \dots, C_t$ として、 $\mathrm{tw}(G) = \max_{1 \leq i \leq t} \mathrm{tw}(C_i)$ が成り立つ。
性質 2
グラフ $G$ に対してマイナー操作（頂点削除・辺削除・辺縮約）を行って得られるグラフを $H$ とすると、 $\mathrm{tw}(H) \leq \mathrm{tw}(G)$ である。
性質 3
グラフ $G$ は次数 $\mathrm{tw}(G)$ 以下の頂点を持つ。
性質 4
頂点集合 $K \subseteq V(G)$ を $G$ のクリークとする。このとき、任意の木分解において $K$ を部分集合として含むバッグが存在する。

アルゴリズム

説明の都合上「木幅が $1$ 以下か？」から順に「木幅が $3$ 以下か？」まで判定するアルゴリズムを与えます。 これらを使うと $\mathrm{tw}(G) \leq 3$ だけでなく $\mathrm{tw}(G) = 3$ かの判定も可能です。

また、性質 1 から、与えられるグラフ $G$ は連結であると仮定します。 コーナーケースが面倒なので、 $n$ が十分大きい（ $n > 5$ ぐらい）ことも仮定します。

木幅が $1$ 以下か？

「木幅が $1$ 以下 $\Leftrightarrow$ 森である」なので簡単に判定できますが、練習としてこれを使わずアルゴリズムを与えます。 （辺が一つもないとき木幅が $0$ になるため、「 $1$ 以下」に注意です。）

まず、与えられたグラフ $G$ に次数 $1$ 以下の頂点が存在しないときを考えます。 これは 性質 3 から $\mathrm{tw}(G) > 1$ を意味するため、即座に No と判定できます。

したがって、次数 $1$ 以下の頂点 $u \in V$ を仮定しましょう。 連結性より、実際には次数はちょうど $1$ です。 実はこのとき、 $u$ の削除が安全であることが示せます。 つまり、グラフ $G$ から $u$ （と $u$ を端点に持つ辺）を削除したグラフを $G'$ として、「 $\mathrm{tw}(G') \leq 1$ ならば $\mathrm{tw}(G) \leq 1$ 」が成り立つことが示せます。 性質 2 からその逆「 $\mathrm{tw}(G) \leq 1$ ならば $\mathrm{tw}(G') \leq 1$ 」が成り立つので、 再帰的に $\mathrm{tw}(G') \leq 1$ を判定すればよいです。

最後に「 $\mathrm{tw}(G') \leq 1$ ならば $\mathrm{tw}(G) \leq 1$ 」の部分を確認します。 幅 $1$ 以下の $G'$ の木分解 $\mathcal{T}$ を任意にとります。 グラフ $G$ において $u$ と隣接している（唯一の）頂点を $v$ とします。 このとき、 $v$ を含むバッグを $\mathcal{T}$ からとり、以下のように新たなバッグを $\mathcal{T}$ へ追加することで幅 $1$ の $G$ の木分解を得られます。

したがって、「 $\mathrm{tw}(G') \leq 1$ ならば $\mathrm{tw}(G) \leq 1$ 」が成り立ちます。

木幅が $2$ 以下か？

上述した「木幅が $1$ 以下か？」の判定アルゴリズムは、簡単に言えば以下の流れでした。

  • 最小次数 $= 1$ $\rightarrow$ その頂点を削除して再帰的に解く。
  • 最小次数 $\geq 2$ $\rightarrow$ No を返す。

実は、「木幅が $2$ 以下か？」も同様のアルゴリズムで解くことができます。

  • 最小次数 $= 1$ $\rightarrow$ その頂点を削除して再帰的に解く。（木幅 $2$ 以下判定でも安全）
  • 最小次数 $= 2$ $\rightarrow$ ここを説明します。
  • 最小次数 $\geq 3$ $\rightarrow$ No を返す。

次数 $2$ の頂点 $u \in V$ を仮定しましょう。 また、 $u$ の隣接頂点 $2$ つを $v, w$ としましょう。 このとき、「$u$ を削除して（存在しなければ）$v, w$ 間に辺を張る」操作が安全となります。 よって同様に再帰的に解いていくことが可能です。

この操作は辺 $\{u, v\}$ を縮約する操作と等価なので、性質 2より操作後のグラフを $G'$ として「 $\mathrm{tw}(G) \leq 2$ ならば $\mathrm{tw}(G') \leq 2$ 」です。 したがってあとはその逆「 $\mathrm{tw}(G') \leq 2$ ならば $\mathrm{tw}(G) \leq 2$ 」を示せばよいです。

この操作における大事な点は、頂点集合 $\{v, w\}$ を $G'$ においてクリークとしたことです。 これにより、（性質 4から） $G'$ の任意の木分解に「 $\{v, w\}$ を部分集合として含むバッグ」を持つことを強制できます。 幅 $2$ 以下のグラフ $G'$ の木分解 $\mathcal{T}$ を任意にとり、 $\mathcal{T}$ から「 $\{v, w\}$ を部分集合として含むバッグ」を任意にとりましょう。 このとき、同様に以下のように新たなバッグを $\mathcal{T}$ へ追加することで幅 $2$ の $G$ の木分解を得られます。

したがって、「 $\mathrm{tw}(G') \leq 2$ ならば $\mathrm{tw}(G) \leq 2$ 」が成り立ちます。

木幅が $3$ 以下か？

木幅 $3$ においても、同様のアルゴリズムです。

  • 最小次数 $= 1$ $\rightarrow$ その頂点を削除して再帰的に解く。（木幅 $3$ 以下判定でも安全）
  • 最小次数 $= 2$ $\rightarrow$ 次数 $2$ の頂点の近傍をクリークとして再帰的に解く。（安全）
  • 最小次数 $= 3$ $\rightarrow$ ここを説明します。
  • 最小次数 $\geq 4$ $\rightarrow$ No を返す。

次数 $3$ の頂点からは様子が変わり、次数 $2$ と同様の操作が安全ではなくなります。 つまり、次数 $3$ の頂点を $u$ として、「 $N(u)$ をクリークにして $u$ を削除する」操作は一般に安全ではなくなります。 操作後のグラフの幅 $3$ 以下の木分解から元のグラフの幅 $3$ 以下の木分解を得ること自体は、同様に $N(u)$ を含むバッグを探し $u \cup N(u)$ のバッグをくっつけることで可能です。 問題は、 $N(u)$ をクリークにすることで木幅が $3$ 以下から $4$ 以上になる場合があることです。 以下の図はその一例です。 左側のグラフは木幅が $3$ ですが、右側のグラフは木幅が $4$ になっています。

しかしながら、次数 $3$ の場合は、このような安全でないケースは「 $N(u)$ の頂点が互いに隣接していない」ケースのみであることが示せます。

補題 1
次数 $3$ の頂点 $u \in V$ について、ある $2$ 頂点 $v, w \in N(u)$ が隣接しているとき、「 $N(u)$ をクリークにして $u$ を削除する」操作は（木幅 $3$ 以下判定について）安全である。

頂点集合 $N(u) \setminus \{v, w\}$ に含まれる唯一の頂点を $x$ とすると、辺 $\{u, x\}$ を縮約して得られるグラフは $G'$ であると観察でき、 性質 2より木幅が大きくならないためです。

このような次数 $3$ の"安全な"頂点がある限り再帰的に解いていくと残るのは、

  • 最小次数が $3$ で、
  • 任意の次数 $3$ の頂点 $u$ について $N(u)$ の頂点は互いに隣接していない

ケースです。 [Arnborg & Proskurowski, 1986] の貢献の一つは、以下の定理です。

Theorem 3.2 [Arnborg & Proskurowski, 1986]
グラフ $G$ が上記の二つの条件を満たし、またその木幅が $3$ 以下だとする。 このとき、グラフ $G$ は「以下の図の $C'$ または $C''$ に同型であって、図中の $u_1,u_2,u_3,x$ に対応する頂点の次数が $3$ である」部分グラフを持つ。

次数 $3$ の頂点をヒントにすれば、愚直に探しても $O(n^3)$ 時間でそのような部分グラフを（存在すれば）見つけることができます。 存在しなければ No と判定できます。 そして実は、この見つけた部分グラフの $u_1,u_2,u_3$ に対応する頂点であれば"安全"というのが、もう一つの大きな貢献です。

Theorem 3.3 [Arnborg & Proskurowski, 1986]
グラフ $G$ の木幅が $3$ 以下であり、「 $C'$ または $C''$ に同型であって、図中の $u_1, u_2, u_3$ に対応する頂点の次数が $3$ である」部分グラフを持つとする。 このとき、各 $u \in \{u_1, u_2, u_3\}$ について、「 $N(u)$ をクリークにして $u$ を削除する」操作は安全である。

したがって、最小次数が $3$ のときも、シンプルなアルゴリズムで $O(n^3)$ 時間で"安全な"頂点 $u$ が見つけられ、近傍をクリークとして再帰的に解いていくことができます。

おまけ

木幅が $4$ 以下か？

同じフレーバーの（Reduction Rule を頑張る）論文があります。

木幅が $2$ ではなく $3$ で抑えられるグラフクラスってあるんですか？

あまり知りません。 木幅が $2$ 以下になることが知られている有名なグラフクラスには、「外平面的グラフ（outerplanar graphs）」「直並列グラフ（series-parallel graphs）」などがあります。 「外1-平面的グラフ（outer 1-planar graphs）」は木幅が高々 $3$ です。 Halin Graph は木幅がちょうど $3$ らしいです。

ただ、「planar $\cap$ 3-tree」、つまり平面的かつ極大な木幅 $3$ のグラフは「Apollonian network」という名前がついていて研究されているようです。 詳しくは知りません。