Reduce set covering problem to vertex covering problem

[GiggleLiu]

No description provided.

[c-allergic]

Vertex Cover

• Given an undirected graph $G =(V,E)$, a vertex cover is a subset($V'$) of $V$ , $S.t.$ $\forall (u,v) \in E$, at least one vertex in $(u,v) \in V'$

Our goal is to find the minimum vertex cover.

Set Cover

Definition

• Given a universe (U) and the collection $\mathcal{S}$ of subsets of (U) , a set cover is subcollection $\mathcal{C} \subseteq \mathcal{S}$ such that the unions of $\mathcal{C}$ covers all the element in (U)

Our goal is to find the minimum set cover

Reduce Vertex Cover to Set Cover

We could map the edges set $E$ as the universe and each vertex $v$ corresponds to a subset $S_v$ that contains all the edges connected to $v$. By doing so, we can convert finding the smallest vertex cover to finding the smallest set cover.

Reduce Set Cover to Vertex Cover

Need Help

[c-allergic]

Solved in #53