HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

NP-complete proof from Dasgupta problem on Kite

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dasguptaproblemkitecompletefromproof

Problem

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

Context

StackExchange Computer Science Q#3509, answer score: 14

Revisions (0)

No revisions yet.