# NP-complete proof from Dasgupta problem on Kite

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.

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'$.
• Why delete the degree 1 nodes? If $G$ has a $k$-clique, then $G'$ has a $2k$-kite, and if $G'$ has a $2k$-kite, then $G$ has a $k$-clique (with the incidental case that if $G$ has a kite so does $G'$). Unless we're asking for an induced subgraph, it's possible that $G$ after deleting the degree 1 vertices still has a $2k$-kite anyway. Sep 12 '12 at 10:05
• Is it necessary to add $v_i$ tails of length k to G'? Wouldn't 1 tail of length k be sufficient? I assume $v_i$ means each vertex in the graph. Apr 5 '19 at 13:13