演算法›Ch5 NP Complete Problems第 8 題/共 30 題
8. NP-Complete、歸約、Vertex Cover、Subset Sum
#AL-05-008中NP-Complete歸約Vertex CoverSubset Sum
The VERTEX-COVER problem is to find a vertex cover of size in a given graph . In the SUBSET-SUM problem, given a finite set and a target , we ask whether there is a subset whose elements sum to . The VERTEX-COVER problem is polynomial-time reducible to the SUBSET-SUM problem. Given an instance of the VERTEX-COVER problem, one can construct a corresponding instance of the SUBSET-SUM problem. Given the following graph (5個頂點 ,邊 構成一個五邊形/五角星) and , is the vertex cover of size . The corresponding set is constructed as the following table (modified based-4 representation, digits for ):
| decimal | ||||||
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 1041 | |
| 1 | 0 | 0 | 1 | 0 | 1284 | |
| 1 | 1 | 0 | 0 | 0 | 1344 | |
| 0 | 0 | 1 | 0 | 0 | 1040 | |
| 0 | 1 | 0 | 1 | 1 | 1093 | |
| 0 | 0 | 0 | 0 | 1 | 1 | |
| 0 | 0 | 0 | 1 | 0 | 4 | |
| 0 | 0 | 1 | 0 | 0 | 16 | |
| 0 | 1 | 0 | 0 | 0 | 64 | |
| 1 | 0 | 0 | 0 | 0 | 256 |
What is the target ? (A) 2389 (B) 3417 (C) 3754 (D) 3758
📄 台大110
▤完整推導請見《WH 資工筆記 · 演算法》Ch5 NP Complete Problems