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

A clique of a graph is the subgraph of the graph. The clique problem is an undirected graph with a goal .Then the clique problem is the subset of vertices that are adjacent to each other and which form a complete graph.

A clique is defined by the following equation $C\left(x\right)=\sum _{i-0}^{w\left(G\right)}{c}_i{x}^i$.

Consider the kite graph with 2n vertices, n vertices form a clique, and the other n vertices are connected by a tail path, and the tail ends are connected to a vertex in the clique. Given a graph G and target g , the kite subgraph with 2g vertices need to be calculated.

By adding $\left|V\right|$vertices to the graph $G\left(V,E\right),$then connecting the $\left|V\right|$vertices with the original vertices in G has a one-to-one correspondence to obtain G'. Then the maximum clique problem can be reduced to the Kite problem.

If G has a kite subgraph with 2g vertices if and only if there is a clique of size g in G when the following conditions satisfy.

There is a clique of size g in $G\Rightarrow G\text{'}$forms a kite subgraph with 2g vertices.

If G' has 2g kite subgraph, then there must have a group of size g.

Thus, the kite is an NP-complete problem.

Therefore, the kite problem is reduced to clique and is NP-complete.