演算法›Ch5 NP Complete Problems
第 8 題/共 30 題
◀ AL 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 kk in a given graph GG. In the SUBSET-SUM problem, given a finite set S⊂NS \subset \mathbb N and a target t∈Nt \in \mathbb N, we ask whether there is a subset S′⊆SS' \subseteq S whose elements sum to tt. The VERTEX-COVER problem is polynomial-time reducible to the SUBSET-SUM problem. Given an instance ⟨G,k⟩\langle G,k\rangle of the VERTEX-COVER problem, one can construct a corresponding instance ⟨S,t⟩\langle S,t\rangle of the SUBSET-SUM problem. Given the following graph GG (5個頂點 v0,v1,v2,v3,v4v_0,v_1,v_2,v_3,v_4,邊 e0,e1,e2,e3,e4e_0,e_1,e_2,e_3,e_4 構成一個五邊形/五角星) and k=3k=3, {v1,v3,v4}\{v_1,v_3,v_4\} is the vertex cover of size k=3k=3. The corresponding set S={1,4,16,64,256,1040,1041,1093,1284,1344}S=\{1,4,16,64,256,1040,1041,1093,1284,1344\} is constructed as the following table (modified based-4 representation, digits for e4e3e2e1e0e_4 e_3 e_2 e_1 e_0):

e4e_4e3e_3e2e_2e1e_1e0e_0decimal
x0x_0001011041
x1x_1100101284
x2x_2110001344
x3x_3001001040
x4x_4010111093
y0y_0000011
y1y_1000104
y2y_20010016
y3y_30100064
y4y_410000256

What is the target tt? (A) 2389 (B) 3417 (C) 3754 (D) 3758

📄 台大110
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch5 NP Complete Problems
本章題號 · 1–20 / 30