ADBlock is blocking some content on the site

# NP-complete proof from Dasgupta problem on Kite

### Question

I am trying to understand this problem from Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, chapter8, Pg281. Problem 8.19

A kite is a graph on an even number of vertices, say \$2n\$, in which \$n\$ of the vertices form a clique and the remaining \$n\$ vertices are connected in a “tail” that consists of a path joined to one of the vertices of the clique. Given a graph \$G\$ and a goal \$g\$, the KITE problem asks for a subgraph which is a kite and which contains \$2g\$ nodes. Prove that KITE is NP-complete.

Any pointers to start with this problem? I am completely lost with it.

### Solution

You can reduce CLIQUE (\$G\$ has a clique of size \$k\$) to KITE: given \$G=(V,E)\$ and \$k\$, just build in polynomial time a new graph \$G'\$ in this way: for each node \$v_i\$ add a tail of \$k\$ new nodes.

If \$G'\$ has a kite of size \$2k\$ then the \$G\$ has a clique of size \$k\$ (the kite without the tail). Added nodes cannot introduce new cliques on G′, so \$G\$ contains exactly the same cliques of \$G'\$.