試題詳解

XIII The VERTEX-COVER problem is to find a vertex cover of the size k in a given graph G. In the SUBSET-SUM problem, given a finite set , we ask whether there is a subset whose elements sum to t. The VERTEX-COVER problem is polynomial-time reducible to the SUBSET-SUM problem. Given an instance ＜ G,_k ＞ of the VERTEX-COVER problem, one can construct a corresponding instance ＜ S,t ＞ of the SUBSET-SUM problem. Given the following graph G and k = 3, {u₁, u₃, u₄} is the vertex cover of size k = 3. The corresponding set S = [1 4, 16, 64 256, 1040, 1041, 1093, 1284, 1344) is constructed as the following table. What is the target t?__ (20)__
(A) 2389
(B) 3417
(C) 3754
(D) 3758