[理工] NP-Complete NPC

[OforU (待)]

(更新：剛剛貼錯題目)
證明NPC:

Given an integer k,
a universe U and a family S = {S1, S2, . . . , Sm}
whose union equals U, where each Si is a subset of U,
find out whether there is a sub-family C ⊆ S of at most size k
whose union is the universe U.

請各位大大給個指點
我目前完全沒想法
想不到要Reduction到什麼東西QQ

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.91.77
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1545659304.A.0C0.html
推 eggy1018: HP reduce 到 HC
啊啊 大大抱歉 剛剛貼錯題目了Orz
※ 編輯: OforU (223.136.91.77), 12/24/2018 22:14:04
推 eggy1018: 加一點p使得p->u,v->p各連到p，形成一instance G’，若
→ eggy1018: 能在此G’中找到HC，因為v->p & p->u連，所以若G’中有H
→ eggy1018: C，則原圖G中一定有由u開始v結束的HP
→ eggy1018: 以上有錯還請告知
推 eggy1018: 第一句改成*加一點p使得p->u,v->p，沒有各連到p
感謝大大前面的回答
→ eggy1018: 我覺得是sunset-sum，可以reduce到3-CNF
大大可否再說詳細
要怎麼看成subset sum problem呢?
※ 編輯: OforU (223.136.91.77), 12/24/2018 22:32:36
推 FRAXIS: 用 Vertex cover reduce 到這問題
推 a66862439: 用subset sum 相對於size去做subset sum為k的問題 不知
→ a66862439: 道這樣可不可解
推 booowei1203: vertex cover -> set cover
→ booowei1203: https://www.clear.rice.edu/comp487/VC_Clique.pdf