Day 132-Q3 | Lex-BFSによる弦グラフ認識

問題

$N$頂点$M$辺の単純無向グラフが与えられる。このグラフが弦グラフ（chordal graph）であるかどうかを判定せよ。弦グラフとは、長さ4以上のすべての閉路が弦（閉路上で隣接しない2頂点を結ぶ辺）を持つグラフのことである。

判定にはLex-BFS（辞書式最大ラベル優先幅優先探索）を用いる。Lex-BFSで頂点訪問順序$\sigma$を求め、その逆順$\sigma^{-1}$が完全消去順序（PEO）になっているかを確認する。逆順がPEOであればグラフは弦グラフである。

入力形式

N M
u_1 v_1
...
u_M v_M

制約

$1 \le N \le 2\times10^5$

$0 \le M \le 2\times10^5$

自己ループ・多重辺なし

入出力例

入力例1

出力例1

Yes

入力例2

出力例2

No

入力例2は弦を持たない4-サイクルそのもので、弦グラフではない。

概念図

ヒント（段階的開示）

ヒント1（方向性）

弦グラフ判定の素朴な方法は「すべての長さ4以上の閉路に弦があるか」を直接確認することだが指数的に大変。弦グラフは「完全消去順序（PEO）」の存在と同値であり、しかもその並べ方は貪欲に作れる。問題はPEOをどう効率よく見つけるかである。

ヒント2（アプローチ）

Lex-BFSは、各未訪問頂点に「これまで訪れた頂点のうち何番目に隣接していたか」を表すラベル（数列）を持たせ、辞書式順序で最大のラベルを持つ頂点を次に訪れる特殊なBFS。単純グラフに対しLex-BFSで得た訪問順序を逆から読むと、それが弦グラフであるときに限りPEOになる（Rose-Tarjan-Lueker, 1976）。①Lex-BFSで順序を作る→②逆順にしてPEOかチェックする、の2段階で判定できる。

ヒント3（誘導）

def is_chordal(n, adj, order):
    peo = order[::-1]
    pos = {v: i for i, v in enumerate(peo)}
    for i, v in enumerate(peo):
        later = [u for u in adj[v] if pos[u] > i]
        if not later:
            continue
        w = min(later, key=lambda x: pos[x])
        for u in later:
            if u != w and u not in adj[w]:
                return False
    return True

模範解答 (Python)

import sys
from collections import defaultdict

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

    label = {v: [] for v in range(1, n + 1)}
    unvisited = set(range(1, n + 1))
    order = []
    for step in range(n):
        v = max(unvisited, key=lambda x: label[x])
        unvisited.discard(v)
        order.append(v)
        for u in adj[v]:
            if u in unvisited:
                label[u] = label[u] + [n - step]

    peo = order[::-1]
    pos = {v: i for i, v in enumerate(peo)}
    chordal = True
    for i, v in enumerate(peo):
        later = [u for u in adj[v] if pos[u] > i]
        if not later:
            continue
        w = min(later, key=lambda x: pos[x])
        adjw = adj[w]
        for u in later:
            if u != w and u not in adjw:
                chordal = False
                break
        if not chordal:
            break

    print("Yes" if chordal else "No")

solve()

Step-by-Step 解説

1Lex-BFSでラベルを育てる
各未訪問頂点は「訪問済み頂点から見て何ステップ目に隣接が確認されたか」を降順に並べたラベル列を持つ。

2辞書式最大の頂点を選び続ける
毎ステップ未訪問頂点の中でラベル辞書式最大のものを訪問し、通常のBFSより強い順序制約を得る。

3逆順をPEO候補にする
グラフが弦グラフであるとき、かつそのときに限り、Lex-BFS順序の逆順が完全消去順序になる（Rose-Tarjan-Lueker定理）。

4PEOの検証
各頂点$v$より後ろにある隣接頂点集合が、直後の隣接頂点$w$を中心にクリークをなしているか確認する。

5計算量
真のLex-BFSは区分リファインメントでO(N+M)。素朴実装はO(N²)〜O(NM)相当だが小〜中規模なら十分実用的。

よくあるミス

ミス	原因	正しい書き方
Lex-BFSの結果をそのままPEOとして使う	「逆順」を取る操作を忘れる	`order[::-1]`のように反転させてからPEO判定にかける
PEOチェックで「直後の頂点」を間違って選ぶ	laterの先頭要素を使ってしまう	`min(later, key=lambda x: pos[x])`で順序上最も近い頂点を選ぶ
Lex-BFSと通常BFSを混同する	ラベルの辞書式比較をせず単純キューでBFSする	ラベル列を明示的に持ち辞書式最大選択を行う
MCSとLex-BFSを同一視する	両方ともPEO候補を与えるが管理方法が異なる	本問では列（リスト）としてラベルを管理し辞書式比較で選ぶLex-BFSを実装する

次のステップ

発展: 区分リファインメント（partition refinement）による真のO(N+M)Lex-BFS実装
発展2: 弦グラフと判定できた場合、PEOで木幅・彩色数・最大独立集合を多項式時間で求める後続問題へ
次回予告: 次回のテーマは今後のセッションで選定

自己評価

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

Day 132-Q3 — Lex-BFSによる弦グラフ認識

問題