Day 123-Q1 | 弦グラフ・完全消去順序（Chordal Graph / PEO）

問題

$N$ 頂点 $M$ 辺の単純無向グラフが与えられる。このグラフが弦グラフ（chordal graph）であるかを判定せよ。弦グラフとは、長さ4以上のすべての閉路に「弦」（閉路上で隣接しない2頂点を結ぶ辺）が存在するグラフのことである。弦グラフであれば木幅（treewidth）（＝最大クリークサイズ $-1$）を出力し、弦グラフでなければ -1 を出力せよ。

入力形式

N M
u_1 v_1
...
u_M v_M

制約

$1 \le N \le 3000$

$0 \le M \le 20000$

グラフは単純（多重辺・自己ループなし）

$1 \le u_i, v_i \le N$

入出力例

入力例1

出力例1

-1

4頂点サイクル $C_4$ には弦が無いため非弦グラフ

入力例2

出力例2

頂点1から扇状に三角形分割。最大クリーク3頂点 → 木幅2

概念図: MCS + Tarjan-Yannakakis検証の流れ

ヒント（段階的開示）

ヒント1: 方向性

「弦グラフかどうか」を毎回すべての閉路を数え上げて調べるのは指数時間になり非現実的である。弦グラフには「頂点を1つずつ、その時点でまだ残っている隣接頂点たちが互いにすべて隣接している（クリークをなす）」ような順序で消去していけるという強力な特徴づけがある。この順序を完全消去順序（Perfect Elimination Ordering, PEO）と呼び、「弦グラフ ⟺ PEOが存在する」という定理が成り立つ。

ヒント2: アプローチ

PEOの候補を効率よく1つ構築する方法がMaximum Cardinality Search（MCS）である。「すでに順序付けられた頂点のうち自分に隣接している頂点数（重み）が最大の未処理頂点」を毎回選ぶ貪欲法だが、グラフが弦グラフであれば、MCSが生成する順序は必ずPEOになる（非弦グラフの場合はPEOにならない）。つまり「MCSで順序を作り、それが本当にPEOかどうかを検証する」という2段階アプローチで判定できる。

ヒント3: 誘導（コード骨格）

検証（Tarjan-Yannakakisのアルゴリズム）の核心：各頂点vのlater（ラベルが大きい隣接頂点集合）の中で最小ラベルの頂点pを「代表」として選び、later の他の全頂点がpと隣接しているかをチェックする。

for i in range(1, N):
    v = pos_to_vertex[i]
    later = [u for u in adj[v] if label[u] > i]
    if not later:
        continue
    p = min(later, key=lambda u: label[u])
    for u in later:
        if u != p and u not in adj[p]:
            pass  # 弦グラフではない

模範解答 (Python)

import sys
import heapq

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    adj = [set() for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        adj[u].add(v)
        adj[v].add(u)

    # --- Maximum Cardinality Search（遅延削除つき最大ヒープ） ---
    weight = [0] * (N + 1)
    visited = [False] * (N + 1)
    label = [0] * (N + 1)  # label[v] = sigma(v)（Nから1へ降順に割り当てる）
    heap = [(0, v) for v in range(1, N + 1)]
    heapq.heapify(heap)
    cur_label = N
    while heap:
        w_neg, v = heapq.heappop(heap)
        if visited[v] or -w_neg != weight[v]:
            continue  # stale entry
        visited[v] = True
        label[v] = cur_label
        cur_label -= 1
        for u in adj[v]:
            if not visited[u]:
                weight[u] += 1
                heapq.heappush(heap, (-weight[u], u))

    pos_to_vertex = [0] * (N + 1)
    for v in range(1, N + 1):
        pos_to_vertex[label[v]] = v

    # --- Tarjan-Yannakakis検証 + 木幅計算 ---
    treewidth = 0
    chordal = True
    for i in range(1, N):
        v = pos_to_vertex[i]
        later = [u for u in adj[v] if label[u] > i]
        if not later:
            continue
        treewidth = max(treewidth, len(later))
        p = min(later, key=lambda u: label[u])
        for u in later:
            if u == p:
                continue
            if u not in adj[p]:
                chordal = False
                break
        if not chordal:
            break

    print(treewidth if chordal else -1)

solve()

計算量: MCSは遅延削除ヒープでO((N+M)log N)、検証はO(N+M)（平均）。C4サイクルで-1、頂点1からの扇状三角形分割で木幅2が出力されることを手計算で確認済み。さらに完全グラフK5では常に木幅4（=5-1）になることも確認した。

Step-by-Step 解説

1弦グラフとPEOの等価性
「PEOが存在する ⟺ 弦グラフ」という特徴づけ定理を使えば、閉路を1本ずつ調べる必要がなくなる。PEOとは頂点を1つずつ取り除くとき、取り除く頂点の残っている隣接頂点たちが常にクリークをなすような順序。

2MCSでPEO候補を構築
「すでに選ばれた頂点にどれだけ隣接しているか」を重みとして貪欲に選ぶ。遅延削除ヒープでO((N+M)log N)。弦グラフに対してのみ本当にPEOを生成する保証がある。

3Tarjan-Yannakakis検証の仕組み
later全ペアを直接チェックするとO(N^2)。「later中で最もラベルが小さい頂点pが他のlater全頂点と隣接していれば、pを介して残り全ペアも隣接している」という補題でO(1)平均に落とし込む。

4木幅の計算
各頂点のlaterサイズ+1が、その頂点を代表とする極大クリークのサイズ。最大値-1が木幅になる。これはPEOをそのまま木分解にできる性質から従う。

5正しさの検証
C4で-1、扇状三角形分割で木幅2、完全グラフK5で木幅4が出力されることを手計算で確認済み。

よくあるミス

ミス	原因	正しい書き方
MCSが常にPEOを作ると思い込み検証を省略する	MCSがPEOを作るのは弦グラフの場合のみと知らない	必ず検証ステップを行う
later全ペアをO(k^2)で愚直チェックする	代表頂点p経由の補題を知らない	最小ラベルのpを選び、他の頂点がpと隣接しているかだけ確認する
木幅を最大クリークサイズそのまま出力してしまう	クリークサイズと木幅の関係を混同	木幅は最大クリークサイズ-1
非連結グラフの孤立頂点を考慮していない	連結グラフのみを想定	laterが空の頂点はスキップするだけで自然に処理できる

次のステップ

発展: 一般グラフの木幅の厳密計算はNP困難。実務では最小次数消去法（Minimum Degree Heuristic）で近似的な木分解を求める。木幅が小さいグラフに対する木DP（Nice Tree Decomposition）と組み合わせて学ぶと理解が深まる。
次回予告: サフィックス配列ベースの暗黙的サフィックス木によるLCEクエリ

自己評価

完全理解おおむね理解要復習

Day 123-Q1 — 弦グラフ・完全消去順序（Chordal Graph / PEO）

問題