VC → HAMPATH

今天看了 VC → HAMPATH, 覺得個 construct 非常巧妙

VC(G, k): exists a k-vertex cover in G?
HAMPATH(G): exists hamilton path in G?

而要做的是, 把 HAMPATH model 去做 VC

由 "cover all edge" 變成 "pass all vertex", 很自然地想到 edge, vertex 互換
想法1: G 的 edge 是 G' 的 node, G 的 node 是 G' 的 edge

問題: 1 個 node 可以連著很多 edge, 但 1 條 edge 只能連著 2 個 node
解決: 每個 node 是 1 條 chain, 即多條 edge




明顯地未完成, 右圖輕易存在 Hamilton path, 但原圖的 VC 最少選 2 個 vertex
最大問題是, 不想條 path 走到一半可以換顏色
現在要加入 VC 中的變數 k: 選取 k 個 vertex, 即要 traverse k 種顏色的路
換句話說, 可以選取 k 條 disjoint path 去 visit 所有 vertex, 而每條 path 的 edge 是同顏色

這時就是最巧妙的一步
目標是把每個點 v 拆成一堆點 v', 並且符合:
1. 只對外連著 2 種顏色的 edge
2. 要走遍 v' 只能是: 選取了顏色1 / 選取了顏色2 / 選取了顏色1, 2

千呼萬喚:




要 visit 圖中的所有點, 有以下方法:




左至右: 只選藍色, 只選紅色, 兩種都選
分別對應一條 edge(u, v), 在 VC 中選取了 {u}, {v}, {u, v}

而且有一點很重要的是, 不能走到一半換顏色
因為若換了的話便一定不能走遍 v'

最後會得到類似以下的東西:

選 1 種顏色 (即選一個 vertex), 就可以走遍它連著的 edge
接下來這步就很簡單了, 因為選 k 個 vertex, 即可 traverse 此 graph component k 次
只要添加 k 個新 node 便可以解決之

References: http://valis.cs.uiuc.edu/~sariel/teach/notes/algos/lec/03_npc_III.pdf