ブログ

先週国際会議 IWOCA 2026 に参加しました． 面白かった発表をいくつか軽く共有します． 宣伝 共著論文を浜田俊祐さん（M2）が発表しました． Best Student Paper も受賞しました！ Minimum Clique Bicoloring Shunsuke Hamada, Yuto Okada, Hirotaka Ono, Yota Otachi 📗会議版 「任意の極大クリークが二色以上含む」頂点の（properとは限らない）彩色をクリーク彩色といい，理想グラフ（perfect graph）周辺のクラスの多くがクリーク2彩色可能という面白い事実が知られています． この論文ではクリーク2彩色の中で片側の色の数を最小化してくださいという問題を導入し，色々なクラス/パラメータでアルゴリズム/困難性を示しました． 個人的に面白かった発表 順番は発表順です． Parameterized Algorithms for Computing MAD Trees Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, André Nichterlein, Camille Richer 📗会議版 📕arXiv版 Minimum Average Distance を達成する全域木を MAD Tree と呼ぶらしいです． つまり，全域木 $T$ で $\sum_{u, v \in V} \mathrm{dist}_T (u, v) / \binom{n}{2}$ を最小化するものです． 結構古くからある問題で，色々なグラフクラスでアルゴリズムが与えられているらしいです． これのパラメータ化計算量を考えましたという論文で，木幅で XP，vertex integrity とモジュラ幅で FPT，スプリットグラフで NP 完全あたりを示していました．...

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