[Solved]: Reducing from Hamiltonian Cycle problem to the Graph Wheel problem cannot be proved vice versa

Problem Detail: 

I saw a proof by Saeed Amiri, 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 Wn+1. It is easy to check that if G has a Hamiltonian cycle then G′ has a Wn+1 wheel (just set v as a center). On the other hand, if G′ has a Wn+1 then there are two possibility:

v is the center of Wn+1→G has a Hamiltonian cycle. Another vertex u is the center of Wn+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 Wn 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.

The proof is valid one way. If a graph has a hamiltonian cycle adding a node to the graph converts it a wheel. If the graph of k+1 nodes has a wheel with k nodes on ring. It has a hamiltonian cycle. BUT IF THE GRAPH OF N nodes has a wheel of size k. Then identifying which k nodes cannot be done in polynomial time. Thus the reduction cannot be done in polynomial time.

Asked By : Ronnie

Answered By : Luke Mathieson

You don't seem to actually be asking a question, but your assertion about the reduction not being polynomial time computable is incorrect.

There are two parts to the reduction which you are confusing (in the literal mixing together sense). Given two problems $A$ and $B$, there is a many-one polynomial-time reduction from $A$ to $B$ if there is a function $f$ such that for every instance $a$ of $A$, $f(b)$ is an instance of $B$ and:

1. $f$ is computable in polynomial time.
2. $a$ is a Yes-instance of $A$ if and only if $f(a)$ is a Yes-instance of $B$.

In Saeed's proof, the function $f$ is copying the graph, adding a new vertex, adding edges between it and all other vertices in the graph and setting $k$ to the size of the initial graph plus one.

This is the part that must be computable in polynomial time. It should be obvious that we can take a graph, add a vertex and some edges, and set a number pretty quickly. Certainly in polynomial time.

Now we have the second part. All this says is that if there is a Hamiltonian cycle in the first graph, then there is a wheel on $k$ vertices in the second graph and vice versa.

We do not have to be able to find either (in any time bound). We only need to know that if one exists, then the other does. You can prove this in any mathematically valid way. It is a purely existential statement. In practice we almost always show that knowing the solution to $f(a)$ would tell us where the solution to $a$ is, but there is no need for it to show how to find it.

This is a lot like showing something is in NP using the verifier definition - we get given a solution and we have to check it. We never say where we got the solution in the first place. Reductions work similarly, we just say that if we can correctly answer Yes or No to one, we can correctly answer the other (out of $a$ and $f(a)$ - note that it doesn't say anything about an arbitrary instance of $B$).

In fact, the whole point of the reduction is to show that we can't find a wheel subgraph in polynomial time unless P=NP.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents