0
$\begingroup$

EDIT: This question is different from the other in a sense that unlike it this one goes into specifics and is intended to solve the problem. In the previous post, the only answer was a hint. In this post, the answer is a proper solution.

Is there a way to "polynomialy" reduce the problem of finding graph wheel $W_{n}$ to the problem of detecting Hamiltonian Cycle (or vice versa) ? The ultimate goal is to show that finding $W_n$ is NP-complete problem. So far I can show that the problem is in NP. To show that I claim that given an input of graph it is possible in polynomial time to check every vertex and to make sure that it has three edges(except the hub): one goes to the hub, one goes to the next vertex and one to the previous vertex. By checking every vertex in this fashion one can make sure the "ticket" indeed represents $W_{n}$.

As far as converting from the Hamiltonian Cycle problem to the problem of fining $W_n$ goes I have encountered that $W_n$ has many Hamiltonian cycles inside it.It is easy to see if one imagines a wheel with a hub and bunch of spokes. Every triangle created by the spokes forms a Hamiltonian cycle as well as any other "closed loop" formed inside a given $W_{n}$.

The intriguing part is the fact that only one vertex is in "the way" and that vertex is the hub. Is the hub of the wheel main culprit in figuring out the conversion ?

Improve this question
$\endgroup$
1
  • $\begingroup$ I still don't see the need for another question: why don't you add a comment to the old question and/or any of the hint answers or suggest an edit, that asks for details? $\endgroup$
    – frafl
    Commented May 12, 2013 at 8:31

1 Answer 1

Reset to default
2
$\begingroup$

We will add one extra vertex $v$ to the graph $G$ and we make new graph $G'$, such that $v$ is connected to the all other vertices of $G$. $G$ has a Hamiltonian cycle if and only if $G'$ has a $W_{n+1}$. It is easy to check that if $G$ has a Hamiltonian cycle then $G'$ has a $W_{n+1}$ wheel (just set $v$ as a center). On the other hand, if $G'$ has a $W_{n+1}$ then there are two possibility:

  1. $v$ is the center of $W_{n+1} \rightarrow G $ has a Hamiltonian cycle.
  2. Another vertex $u$ is the center of $W_{n+1}$ in $G'$. So both $deg(u) = deg(v) = n$. Then we can change the labeling of this two vertices (actually they are equivalence under isomorphic), now we have again first possibility.

P.S1: By $W_n$ I mean the wheel with $n$ vertex.

P.S2: In this proof we say if we fix $k=n+1$ (size of the artificial graph), then the problem is NP-Complete in this restricted version, So it's also NP-Complete in the case $k$ is as input parameter.

Improve this answer
$\endgroup$
17
  • $\begingroup$ Thanks for the idea, but unfortunately it does not work because the questions asks to find a wheel and not to show whether the entire graph is a wheel. Thus, adding a vertex that connects to all other vertices creates a something other than a wheel. $\endgroup$
    – 372
    Commented May 10, 2013 at 16:38
  • $\begingroup$ ... Here is an example where this approach does not work: say we have an original graph that contains a rim subgraph (i.e. wheel without hub and spokes). Adding a vertex $v$ that connects to all other vertices will effectively create a wheel and thus we get a false alarm when checking for hamiltonian cycles. $\endgroup$
    – 372
    Commented May 10, 2013 at 17:13
  • $\begingroup$ ... hmm actually nevermind... I figured that what you proposed is translation from Hamiltonian Cycle problem to the wheel problem. I just still can't wrap my head around some NP-complete translation concepts and thus can't fully grasp the concept behind. Either way, thanks for the solution $\endgroup$
    – 372
    Commented May 10, 2013 at 18:20
  • $\begingroup$ @AdamPflepinsky, you said " not to show whether the entire graph is a wheel", but I didn't show that the entire graph is a wheel. I show that for every graph G I can make another graph G'. Such that G has hamiltonian circuit, if and only if G' has a $W_n$. To prove NP-Completeness of problems we don't need to find a wheel in original graph. Normally we will create a new artificial graph and we say if I could solve my problem in new created graph then I can solve specific NP-complete problem on original one. $\endgroup$
    – user742
    Commented May 10, 2013 at 20:02
  • $\begingroup$ Say our graph G is a graph such that it has a ring (wheel without hub and spokes) that has two tails (tails being consequently connected vertices such that they form a straight line). So the G does not have a Hamiltonian Cycle. However, after adding the vertex $v$ that connects to all other vertices the graph $G'$ becomes such that it has vertex $v$ connected to all the vertices inside the ring and tails. If we look at the ring alone we see that $v$ serves as a hub and edges to the ring vertices serve as spokes. Thus, effectively we have a wheel that is a subgraph of $G'$ $\endgroup$
    – 372
    Commented May 10, 2013 at 20:21

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