Solution Found!
A kite is a graph on an even number of vertices, say 2n, in which n of the vertices form
Chapter 8, Problem 8.19(choose chapter or problem)
A kite is a graph on an even number of vertices, say \(2 n\), 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 and a goal \(g\), the KITE problem asks for a subgraph which is a kite and which contains \(2 g\) nodes. Prove that KITE is NP-complete.
Questions & Answers
QUESTION:
A kite is a graph on an even number of vertices, say \(2 n\), 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 and a goal \(g\), the KITE problem asks for a subgraph which is a kite and which contains \(2 g\) nodes. Prove that KITE is NP-complete.
ANSWER:
Step 1 of 2
A Kite graph is defined as a graph with \(2n\) number of vertices in which \(n\) vertices form a clique and the remaining vertices are connected to a vertex which is connected to one of the vertices in the clique.
A clique is a subgraph of graph \(G\), in which each pair of the vertices are connected by an edge. Clique problem with goal \(k\) is defined as the problem to find a clique with a minimum \(k\) vertices from the given graph \(G\). Clique problem is NP-Complete.