木幅3の判定
この記事は 木 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) \}$ の組であって、以下の条件をすべて満たすものです。...