[Solved]: Proving that finding wheel subgraphs is NP-complete

Problem Detail: 

Can you help me with this problem ?

Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ nodes form a cycle and a $i+1$st node is connected to all other nodes, resulting in $2i$ edges) is NP-complete.

Asked By : 372

Answered By : Aryabhata

Hint: Hamiltonian Cycle is $NP$-Complete.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11505

 Ask a Question

 Download Related Notes/Documents