11.21

Reduction idea
Given an arbitrary instance of CLIQUE – a graph [math]H=(V,E)[/math] and an integer [math]g[/math] – we build, in polynomial time, a graph [math]G[/math] such that
   H has a clique of size [math]g[/math]   ⇔  G contains a kite on [math]2g[/math] vertices.

Construction of G
For every vertex [math]v_i\in V[/math] introduce [math]g[/math] fresh vertices [math]s_{i,1},\dots ,s_{i,g}[/math] and the edges
   1. [math]v_i s_{i,1}[/math]
   2. [math]s_{i,1}s_{i,2},\,s_{i,2}s_{i,3},\dots ,s_{i,g-1}s_{i,g}[/math]
No other new edges are added, i.e. the path vi-si,1-…-si,g is private to [math]v_i[/math]. All original edges of H are kept unchanged. The size of G is [math]|V|+g|V| \le (g+1)|V|[/math], hence the reduction is polynomial.

⇒ If H has a g-clique
Let [math]C=\{v_{i_1},\dots ,v_{i_g}\}[/math] be the clique. Pick any vertex, say [math]v_{i_1}[/math], and take the g-vertex path
si₁,1-si₁,2-…-si₁,g. The subgraph induced by [math]C\cup\{s_{i_1,1},\dots ,s_{i_1,g}\}[/math] is exactly a kite: • the g vertices of C are a clique (they were in H); • the remaining g vertices form a path joined only to [math]v_{i_1}[/math]. Thus G contains the required 2g-vertex kite.

⇐ If G has a 2g-vertex kite
Let the kite’s clique be [math]C[/math] and its tail be t₁-…-tg with [math]t_1[/math] adjacent to exactly one vertex [math]v[/math] of C. Because only vertices of the form [math]s_{i,1}[/math] are incident to exactly one original vertex, t₁=t_{v,1} and the whole tail lies in the private path of v. Consequently every vertex of C is an original vertex of H, and all pairs inside C are still adjacent (no extra edges were created). Hence C is a size-g clique in H.

Pseudocode of the reduction
build_kite_instance(H=(V,E), g):
  G ← (V, E) # start with H
  for each v in V:
    prev ← v
    for j = 1 … g:
      s ← new_vertex()
      add_edge(prev, s) # v–s₁ or sⱼ–sⱼ₊₁
      prev ← s
  return G, g

Conclusion
We have reduced CLIQUE to MAX-KITE in polynomial time; therefore MAX-KITE is NP-hard. (Membership in NP is immediate, so the decision version is NP-complete.)

Back to Chapter 11