)
. Thus, we can use this fact to check in
polynomial time.
Definition
Given an undirected graph G, there exists a set CL ⊆ V such that for every two vertices in V, there exists an edge connecting the two.
Polynomial Certifier
Question: Given an undirected graph G, and an integer k. Does there exist a set CL ⊆ V of size k, such that for every two vertices in V, there exists an edge connecting the two?
)
. Thus, we can use this fact to check in
polynomial time.
Reduction from Independent Set by Equivalence
Given an instance of Independent Set with graph G = (V,E) and
a bound k, construct the complement graph G = {V,E} of G, where
E = {(u,v)|u,v 
V,(u,v) ⁄ E}. Obviously this can be done in polynomial
time.
Claim 4.13.5.1. Independent Set lep Clique
G has an Independent Set IS of size at most k if and only if G has a clique
CL = IS of size at least |V |- k.
G has an Independent Set IS of size at most k ⇒G has a clique CL = IS of size at least |V |- k.
Proof. __
G has a clique CL = IS of size at least |V |-k ⇒ G has an Independent Set IS of size at most k.
Proof. __
Reduction from Vertex Cover by Equivalence
Given an instance of Vertex Cover with graph G = (V,E) and a bound k, construct
the complement graph G = {V,E} of G, where E = {(u,v)|u,v V,(u,v) ⁄ E}.
Obviously this can be done in polynomial time.
Claim 4.13.5.2. Vertex Cover lep Clique
G has a vertex cover VC of size at most k if and only if G has a clique
CL = V \ V C of size at least |V |- k.
G has a vertex cover VC of size at most k ⇒G has a clique CL = V \V C of size at least |V |- k.
Proof. Suppose that G has a vertex cover V C with a size at most k. Then
∀u,∀v CL = V \ V C,(u,v) ⁄ E; otherwise, one of u or v would be in VC,
contradicting the assumption that u and v are in CL. In G, if (u,v) ⁄ E, then
(u,v) E, which is the definition of a clique. Thus, CL is a clique of size at
least |V |- k. __
G has a clique CL = V \V C of size at least |V |-k ⇒ G has a vertex cover VC of size at most k.
Proof. Conversely, suppose G has a clique CL = V \ V C with a size at least
|V |- k. For all edges (u,v) E, (u,v) ⁄E, which implies that one of u or v is
not in the clique CL. Then, at least one of u or v is in VC, guaranteeing that
at least one endpoint of edge (u,v) E is in VC. Thus, VC is a vertex cover.
Since clique CL has a size at least |V |- k, |V C| has a size at most k. __
