9
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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'$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson Sep 12 '12 at 10:05
  • $\begingroup$ @LukeMathieson: you are right, it is not an induced subgraph. I changed the answer $\endgroup$ – Vor Sep 12 '12 at 10:41
  • $\begingroup$ 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. $\endgroup$ – DanGoodrick Apr 5 '19 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.