Day 146-Q2 | Nemhauser-Trotter定理

問題

$N$ 頂点 $M$ 辺の無向グラフ $G$ が与えられる。最小頂点被覆問題のLP緩和の最適値（$\sum_v x_v$ の最小値、$x_v\in[0,1]$、各辺$(u,v)$で$x_u+x_v\ge1$）を求めよ。

構成法（Nemhauser-Trotter）:

各頂点$v$を$v_L,v_R$の2複製に分け、二部グラフ$H$（$2N$頂点）を作る。
$G$の各辺$(u,v)$について$H$に$(u_L,v_R)$と$(v_L,u_R)$を追加する。
$H$の最大マッチングのサイズを$\mu$とする（König定理より最小頂点被覆サイズも$\mu$）。
LP緩和の最適値は$\mu/2$に等しい。

直感: $H$の任意の最小頂点被覆$C$（サイズ$\mu$固定）で、各頂点$v$の被覆されたコピー数$c_v\in\{0,1,2\}$として$x_v^\ast=c_v/2$と定めるとLP制約を満たし、$\sum_v x_v^\ast=|C|/2=\mu/2$（$C$の選び方に依らず一定）。

入力形式

N M
u_1 v_1
:
u_M v_M

制約

$1 \le N \le 12$

$0 \le M \le N(N-1)/2$

$0 \le u_i,v_i

誤差 $10^{-6}$ 以内（値は必ず0.5の整数倍）

入出力例

入力例1

出力例1

2.500000

長さ5の奇閉路。二重被覆グラフは長さ10の1本のサイクルになり最大マッチング=5、LP値=5/2=2.5。真の整数最適(3)との差が整数ギャップ。

概念図：二部二重被覆グラフの構築

ヒント（段階的開示）

ヒント1（方向性）

頂点被覆の整数計画はNP困難だがLP緩和は多項式時間で解ける。頂点被覆特有の「各制約が2変数のみ」という構造を利用すればグラフアルゴリズムだけでLP最適値を厳密に求められる。

ヒント2（アプローチ）

各頂点を左右2つの役に分身させ、元の辺関係を二部グラフの辺として埋め込む（$u_L$-$v_R$、$v_L$-$u_R$）。この二部グラフ上で最小頂点被覆（＝最大マッチングのサイズ、König定理）を求めれば、その半分がLP最適値になる。

ヒント3（誘導）

def bipartite_max_matching(n_left, n_right, adj):
    match_right = [-1] * n_right
    def try_kuhn(u, visited):
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                if match_right[v] == -1 or try_kuhn(match_right[v], visited):
                    match_right[v] = u
                    return True
        return False
    matching_size = 0
    for u in range(n_left):
        visited = [False] * n_right
        if try_kuhn(u, visited):
            matching_size += 1
    return matching_size

辺$(u,v)\in G$ごとに`adj[u].append(v)`（$u_L$-$v_R$）と`adj[v].append(u)`（$v_L$-$u_R$）を追加し、最大マッチングを$\mu$として`mu/2`を出力する。

模範解答 (Python)

import sys

def bipartite_max_matching(n, adj):
    match_right = [-1] * n

    def try_kuhn(u, visited):
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                if match_right[v] == -1 or try_kuhn(match_right[v], visited):
                    match_right[v] = u
                    return True
        return False

    matching_size = 0
    for u in range(n):
        visited = [False] * n
        if try_kuhn(u, visited):
            matching_size += 1
    return matching_size


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    adj = [[] for _ in range(N)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)

    mu = bipartite_max_matching(N, adj)
    print(f"{mu / 2:.6f}")

main()

Step-by-Step 解説

1二部二重被覆グラフの構築
各辺$(u,v)$について$H$に$u_L$-$v_R$と$v_L$-$u_R$の2本を追加する。

2最大マッチング（Kuhn法）
$N\le12$なので素朴な増加路DFS($O(NM)$)で十分。

3König定理による最小頂点被覆サイズ
二部グラフでは最大マッチングのサイズ$\mu$と最小頂点被覆のサイズが一致する。

4なぜ答えが$\mu/2$で一意に定まるか
任意の最小頂点被覆$C$で$\sum_v c_v=|C|=\mu$（$C$の各要素はちょうど1つの$v$のコピー）。$x_v^\ast=c_v/2$より$\sum x_v^\ast=\mu/2$は$C$の選び方に依らない。

5入力例の検証
5-サイクルの二重被覆は10-サイクル1本になり最大マッチング=5、LP最適値=2.5。整数最適(3)との差が整数ギャップ。

よくあるミス

ミス	原因	正しい書き方
二部グラフの辺を$(u_L,v_R)$のみ追加し$(v_L,u_R)$を忘れる	無向辺を片方向としか捉えない	各辺で必ず2本とも追加する
答えを整数$\mu$のまま出力する	LP緩和値が半整数であることを見落とす	`mu/2`として小数で出力
Kuhn法の`visited`配列をループ外で1回だけ初期化する	増加路探索のたびのリセットを忘れる	左側頂点1つ処理するたびに作り直す
頂点被覆の実際の集合まで復元しようとする	問題が「サイズの合計」のみを問うことを見落とす	マッチングサイズだけで答えが出ることに気づく
$N=1,M=0$のような自明ケースで例外になる	空グラフを想定していない	`adj`が空でも0を返すため問題なし

次のステップ

発展: 実際に最小頂点被覆を復元し、各頂点の$x_v^\ast\in\{0,0.5,1\}$を個別出力せよ。$x_v^\ast=0.5$の頂点だけの縮小グラフで探索すれば$2k$頂点カーネル化になる。
次回予告: Cole-Vishkinアルゴリズム（森の彩色数縮小・O(log* N)反復の決定的対称性破壊）

自己評価

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

Day 146-Q2 — Nemhauser-Trotter定理（頂点被覆LP緩和・最大流帰着）

問題