Question

Problem: Clique

In this problem IS stands for Independent Set.

The usual IS problem, that we showed in class in NP-complete is as follows:

Input: Unidrected graph G(V, E) and number k, with 1 ≤ k ≤ n.
Output: YES if G has an independent set of containing at least k vertices.
  NO if all independent sets of G contain strictly less than k vertices.

Definition: Let G(V, E) be an undirected graph and let V ′ be a proper subset of vertives of V : V ′ ⊂ V . We sat thay V is a clique of size k=|V′| if and only if, for all u∈V′ and for all u != v in V′ the edge{u,v}∈E.

Now define the Clique problem as follows:

Input: Unidrected graph G(V, E) and number k, with 1⌉ ≤ k ≤ n.
Output: YES if G has a clique containing at least k vertices.
  NO if cliques of G contain strictly less than k vertices.

Show that IS≤ pCLIQUE.

Answer 1

We use a reduction from VERTEX COVER. Given an instance (G = (V, E), k) of VC we transform it to an instance (G′ = (V ′, E′), k) of DS as follows. First we remove all isolated vertices from G (clearly, they are not necessary in any VC since they have no edges). G′ is similar to G, with a vertex added for each edge, and connected to both sides of the original edge. Formally, V ′consists of all the non-isolated vertices in V and a vertex ve ∀e ∈ E, and E′ consists of E, and the new edges (ve,u) and (ve,w) ∀e = (u,w) ∈ E. The reduction can clearly be done in polynomial time.

⇒ LetU beavertexcoverofG. WeshowthatitisalsoadominatingsetinG′. For∀v∈V′\Uthere are two possibilities

1. If v ∈ V then, since it is not an isolated vertex, there is an edge (u,v) ∈ E. Since U is a vertex cover and v ∈/ U, we have u ∈ U, so v has a neighbour in U.

2. v = ve for some edge e = (u,w) ∈ E. Since U is a vertex cover, u ∈ U or w ∈ U, so vhas a neighbour in U.

⇐ Suppose that U is a dominating set in G′ of size ≤ k. We first get rid of vertices in Ucorresponding to edges of G. If ve ∈ U for some edge e = (u, w) ∈ E, then we replace it withu. Note that:

1. Note that the size of U does not increase in this process.

2. The neighbours of a vertex ve for e = (u,w) are only u and w. Thus, by removing vefrom U, the only vertices that might become uncovered are ve, u and w, but they are covered by u. Therefore U remains a dominating set.

∀e = (u,w) ∈ E, U must contain u or w (otherwise ve has no neighbour in U). Thus, U is a dominating set in G.