2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This object is also often referred to as the Wheel on $n$ vertices, and denoted $W_n$. $\endgroup$ – Pål GD Apr 23 '13 at 14:01
  • $\begingroup$ @Raphael,Hamiltonian Cycle approach does not seems to be valid because for this problem one needs to show that finding certain SUBGRAPH is an NP-Complete problem. Hamiltonian Cycle does not deal with subgraphs... Any other ideas ? $\endgroup$ – 372 May 10 '13 at 21:03
5
$\begingroup$

Hint: Hamiltonian Cycle is $NP$-Complete.

$\endgroup$
1
$\begingroup$

Following the advice in our reference post, check out related NP-complete problems in order to find a suitable reduction partner.

Hamiltonian cycle does indeed look promising: note that $W_n$ contains a simple cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.