Day 134-Q5 | 頂点被覆問題の2-近似アルゴリズム

問題

$N$頂点$M$辺の無向単純グラフが与えられる。辺は$1$から$M$まで番号が振られた順に並んでいる。次の手続きで頂点被覆を1つ構成せよ。

各頂点に使用済みフラグを持たせ初期状態は未使用。辺を番号の昇順に見ていき、両端点がともに未使用であればマッチングに加え両方を使用済みにする。すでにどちらかが使用済みの辺は読み飛ばす。全辺を見終えたら、使用済みの頂点全体を頂点被覆として出力する。

構成された頂点被覆に含まれる頂点数と、頂点番号を昇順に出力せよ。

入力形式

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 \le u_i,v_i \le N$、$u_i\neq v_i$

多重辺なし

入出力例

入力例1

出力例1

4
1 2 5 6

$(1,2)$を採用し$1,2$を使用済みに。$(1,3),(1,4),(1,5)$は$1$使用済みで読み飛ばし。$(5,6)$を採用。結果$\{1,2,5,6\}$。厳密な最小頂点被覆は$\{1,5\}$（サイズ2）で、貪欲解はちょうど2倍。

概念図

ヒント（段階的開示）

ヒント1（方向性）

最小頂点被覆そのものはNP困難。本問が要求するのは厳密解ではなく指定された貪欲手続きの結果。まずは手続きをそのまま素直にシミュレートする。

ヒント2（アプローチ）

辺を順に見て両端点未使用なら採用し両方を使用済みにする操作は極大マッチングを貪欲に作っていることに等しい。マッチングに使われた頂点全部が頂点被覆になる理由を考えよ。

ヒント3（誘導）

used = [False] * (N + 1)
for u, v in edges:  # 1-indexed
    if not used[u] and not used[v]:
        used[u] = True
        used[v] = True
cover = [i for i in range(1, N + 1) if used[i]]

正当性の鍵: もしカバーされない辺$(a,b)$が残っていたら、その辺は「マッチングに追加できたはず」なので、マッチングが極大であるという前提に矛盾する。

模範解答 (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

    used = [False] * (N + 1)
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        if not used[u] and not used[v]:
            used[u] = True
            used[v] = True

    cover = [i for i in range(1, N + 1) if used[i]]
    print(len(cover))
    print(*cover)


main()

Step-by-Step 解説

1手続きは極大マッチングを作る
採用された辺の集合$P$はマッチングであり、採用されなかった辺は必ず端点のどちらかが既に使用済みなので、$P$に辺を追加する余地はない（極大）。

2使用済み頂点集合が頂点被覆になる理由
どの辺も、採用されたなら両端点使用済み、されなかったなら処理時点でどちらかが既に使用済み。よって全ての辺が少なくとも1端点でカバーされる。

32-近似の証明
使用済み頂点数は$2|P|$。どんな頂点被覆もマッチング$P$の各辺につき少なくとも1端点を含む必要があるため$\mathrm{OPT}\ge|P|$。よって$2|P|\le2\,\mathrm{OPT}$。

4計算量
辺を1回スキャンするだけで$O(N+M)$。

5精度とコストのトレードオフ
最大マッチングを使えば下界がタイトになる（二部グラフではKönigの定理で厳密解に一致）が、一般グラフでは実装コストが跳ね上がる。極大マッチングは貪欲に$O(N+M)$で作れる。

よくあるミス

ミス	原因	正しい書き方
「極大マッチング」と「最大マッチング」を混同	字面が似ている	極大=これ以上追加できない、最大=辺数最多、を区別する
厳密な最小頂点被覆を求めようとする	NP困難な厳密最適化を連想	問題文が指定した貪欲手続きをそのままシミュレートする
辺の走査順を無視し独自のヒューリスティックを使う	「貪欲」から自由な工夫を連想	入力の辺番号順を厳密に守る（手続きの結果を一意に問うている）
近似保証を疑い勝手に後処理で頂点を削る	$2\,\mathrm{OPT}$以下という保証を信じられない	Step3の証明の通り保証されているため後処理は行わない
出力の頂点番号を使用済みにした順のまま出す	昇順出力の仕様を見落とす	`range(1, N+1)`で昇順に走査して収集する

次のステップ

発展: 二部グラフに限定しHopcroft–Karp法で最大マッチングを求め、Königの定理で厳密な最小頂点被覆を復元する実装を書き、本問の2-近似と比較せよ。
発展2: 頂点に重みが付いた重み付き頂点被覆に対する2-近似アルゴリズム（LP緩和と丸め）を調べ、本問との関係を整理せよ。
次回予告: 次回のテーマは今後のセッションで選定

自己評価

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

Day 134-Q5 — 頂点被覆問題の2-近似アルゴリズム（Vertex Cover 2-Approximation）

問題