Vertex Cover

4.13.1 Vertex Cover

Definition

Given undirected graph, G = (V,E). There exists a subset A ⊆ V , such that A is a vertex cover, if every edges in G has at least one endpoint in A.

Polynomial Certifier

Question: Given undirected graph, G = (V,E) and a number k. Does there exist a vertex cover of size at most k?

Input: Given an undirected graph G and an integer k
Certificate: A subset of V, A ⊆ V
Certifier: Check if A is a vertex cover of size ≤ k in G.
Time Complexity: We check if all nodes in A cover all edges in G, that is O(n ⋅ m).

Reduction from Independent Set by Equivalence

For given graph G, and given Vertex Cover set A, we construct a Independent Set by removing all elements in A from V. That is, (V \ A) is Independent Set. Obviously, the construction can be done in polynomial time in terms of |V |.

Figure 4.13.1:

Graph that shows Vertex Cover and Independent Set

Claim 4.13.1.1. Independent Set ≡_p Vertex Cover.
VC is a Vertex Cover in G, if and only if IS = (V \V C) is an Independent Set in G.

VC is a Vertex Cover in G ⇒ IS = (V \ V C) is an Independent Set in G.

Proof. Suppose VC is a vertex cover. Consider any two nodes u and v in (V \A). If they were joined by an edge e, then neither end of e would lie in VC, contradicting our assumption that VC is a vertex cover. It follows that no two nodes in IS are joined by an edge, and so IS is an independent set. __

IS = (V \ V C) is an Independent Set in G ⇒ VC is a Vertex Cover in G.

Proof. Suppose IS is an independence set. Consider an arbitrary edge e = (u,v). Since IS is independent, u and v cannot both be in IS; so one of them must be in VC. It follows that every edge has at least one end in VC, and so VC is a vertex cover. __

[next] [front] [up]