Vertex cover reduces to set cover _reduce

从来好事天生俭，自古瓜儿苦后甜。这篇文章主要讲述Vertex cover reduces to set cover相关的知识，希望能为你提供帮助。

目录

1.1 Vertex cover
- 1.1.1 VERTEX-COVER ≤ P SET-COVER
- 1.1.2 证明充分性
- 1.1.3 证明必要性

1.1 Vertex cover例子：
U =1, 2, 3, 4, 5, 6, 7
Sa =3, 7Sb =2, 4
Sc =3, 4, 5, 6Sd =5
Se =1Sf=1, 2, 6, 7
k = 2（Sc和Sf可以覆盖完原集合U）
1.1.1 VERTEX-COVER ≤ P SET-COVER
Pf. Given a VERTEX-COVER instance G = (V, E) and k, we construct a
SET-COVER instance (U, S, k) that has a set cover of size k iff G has a
vertex cover of size k.
Construction：

Universe U = E.
Include one subset for each node v ∈ V : Sv = e ∈ E : e incident to v .

文章图片

文章图片

1.1.2 证明充分性
Pf. ? Let X ? V be a vertex cover of size k in G.
Then Y =Sv : v ∈ Xis a set cover of size k.
“no” instances of VERTEX-COVER are solved correctly！
一个实列：

文章图片

如果我们选择f与c结点那么恰好可以对应到一个子集合覆盖。
但是如果我们顶点覆盖的点选择f和d,那么对应的子集合覆盖为Sf和sd显然这两个集合不能覆盖原集合U。
结论：无充分性！
1.1.3 证明必要性
【Vertex cover reduces to set cover】Pf. ? Let Y ? S be a set cover of size k in (U, S, k).