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.

Improve this question
$\endgroup$
2
  • $\begingroup$ This object is also often referred to as the Wheel on $n$ vertices, and denoted $W_n$. $\endgroup$ Commented Apr 23, 2013 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$ Commented May 10, 2013 at 21:03

2 Answers 2

Reset to default
5
$\begingroup$

Hint: Hamiltonian Cycle is $NP$-Complete.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.