Day 147-Q5 | Max-Cutの脱乱択化

問題

$N$頂点$M$辺の無向単純グラフ（重みなし）が与えられる。頂点を色$0/1$に塗り分け、異なる色を結ぶ辺（カット辺）の本数を最大化したい。頂点$0,1,\dots,N-1$の順に、以下の決定的な規則で色を確定させよ。

頂点$v$を処理する時点で、$v$より番号が小さく既に確定済みの隣接頂点のうち色0の個数を$\text{same}_0$、色1の個数を$\text{same}_1$とする。$\text{same}_1\ge\text{same}_0$なら色0、そうでなければ色1を選ぶ（同点は色0）。

この手続きにより最終カット本数は必ず $\lceil M/2\rceil$ 以上になることが証明されている（乱択1/2近似の期待値保証を、悪化させない選択の連続で決定的に再現するため）。

入力形式

N M
u_1 v_1
:
u_M v_M

制約

$2 \le N \le 15$

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

多重辺・自己ループなし

入出力例

入力例1

出力例1

0 1 0 0 1
5

概念図：頂点を順に確定させ5/6本をカット

ヒント（段階的開示）

ヒント1（方向性）

各頂点を独立に確率1/2でランダムに色を塗ると、辺$(u,v)$がカットされる確率はちょうど1/2なので期待カット本数は$M/2$。この期待値の議論を、乱数を1回も使わずに同じかそれ以上の値を保証する決定的アルゴリズムに変換できないか考える。

ヒント2（アプローチ）

頂点を1つずつ確定させるとき、「まだ確定していない頂点は今後ランダムに決まる」と仮定した条件付き期待値を考える。この期待値を悪化させないように各頂点の色を選べば、最終的な条件付き期待値（＝実際のカット本数）は初期値$M/2$を下回らない。

ヒント3（誘導）

def derandomized_maxcut(N, adj):
    color = [None] * N
    for v in range(N):
        same0 = sum(1 for u in adj[v] if u < v and color[u] == 0)
        same1 = sum(1 for u in adj[v] if u < v and color[u] == 1)
        color[v] = 0 if same1 >= same0 else 1
    return color

模範解答 (Python)

import sys

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

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

    color = [None] * N
    for v in range(N):
        same0 = 0
        same1 = 0
        for u in adj[v]:
            if u < v:
                if color[u] == 0:
                    same0 += 1
                else:
                    same1 += 1
        color[v] = 0 if same1 >= same0 else 1

    cut_count = sum(1 for u, v in edges if color[u] != color[v])

    print(' '.join(map(str, color)))
    print(cut_count)


main()

Step-by-Step 解説

1頂点0の処理
確定済み隣接頂点がないため$\text{same}_0=\text{same}_1=0$で同点、規則により色0。

2頂点1〜4の処理
頂点1は隣接する頂点0(色0)から$\text{same}_0=1,\text{same}_1=0$で色1。頂点2は頂点0(色0)・頂点1(色1)から同点で色0。頂点3は頂点1(色1)のみから色0。頂点4は頂点2(色0)・頂点3(色0)から$\text{same}_0=2$で色1。最終色は`[0,1,0,0,1]`。

3カット本数の確認
6本のうち異なる色は5本、同色は(0,2)の1本のみ。カット本数5は下限保証$\lceil6/2\rceil=3$を上回る。

4悲観的推定量の直感
各頂点を確定するたび2つの選択肢のどちらかは必ず条件付き期待値を下げない（両者の平均が確定前の期待値と一致するため）。これを全頂点で繰り返すと最終カット本数は初期期待値$M/2$以上になる。

よくあるミス

ミス	原因	正しい書き方
未確定の隣接頂点まで数えてしまう	`adj[v]`を全て走査し$v$より後の頂点も含める	`u < v`の条件で確定済みの頂点だけに絞る
同点のとき色1を選んでしまう	タイブレーク規則を決めずに実装する	問題文通り「同点なら色0」を固定する
新たにカットされる本数とその頂点の次数を混同する	$\text{same}_0,\text{same}_1$の意味を取り違える	$\text{same}_1$は色0を選んだ場合に新たにカットされる本数であることを整理する
Goemans-Williamsonの0.878近似と同じだと誤解する	SDPを使う本物のGW法との違いを理解していない	本手法は乱択1/2近似の脱乱択化であり保証は$M/2$以上に留まる
カット本数を頂点走査で二重カウントする	無向辺の走査方法を誤る	`edges`リスト（各辺1回）を走査して`color[u]!=color[v]`を数える

次のステップ

発展: 真の最大カット（全探索・bitmask DP）を求め、脱乱択化アルゴリズムとの近似率を実測せよ。
次回予告: 次のMaster Levelローテーションへ続く。

自己評価

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

Day 147-Q5 — Max-Cutの脱乱択化（Method of Conditional Expectations）

問題