13
$\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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
14
$\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'$.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Sep 12, 2012 at 10:05
  • $\begingroup$ @LukeMathieson: you are right, it is not an induced subgraph. I changed the answer $\endgroup$
    – Vor
    Commented Sep 12, 2012 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
    Commented Apr 5, 2019 at 13:13
  • 1
    $\begingroup$ @DanGoodrick You don't know which vertices from G constitute the clique of size $k$, so, for this particular problem formulation, you must attach a tail to every vertex in $V$ to ensure that no matter which vertices constitute the clique, the tail is attached. $\endgroup$
    – Josh
    Commented Apr 18, 2022 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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