Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/#!/StackCompSci/status/245854952763846657
edited tags
Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393
mathjax
Source Link
Vor
Vor
  • 12.7k
  • 1
  • 30
  • 62

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 kitekite is a graph on an even number of vertices, say 2n$2n$, in which n$n$ of the vertices form a clique and the remaining n$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$g$, the KITE problem asks for a subgraph which is a kite and which contains 2g$2g$ nodes. Prove that KITE is NP-complete.

Any pointers to start with this problem? I am completely lost with it.

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

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.

Source Link
John
John
  • 233
  • 1
  • 2
  • 6

NP-complete proof from Dasgupta problem on Kite

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