Re: A letter want to disprove my paper which submitted recently

Zhu Guohun wrote:
Hi, Dear all,

After I sumitted a draft to arxiv.org " The Complexity of
Determining Existence a Hamiltonian Cycle is O(n^3)".

To my surprise, a letter send to me and asked to withdraw this paper
and comments that he disprove my last paper in "http://arxiv.org/abs/
0704.0309".

Follows is part of the my received email

"the key point seems to be that in an earlier paper you proved that
Ham. cycle for graphs such that the sum of the in and the outdegree of
each node is at most 2 is in P. (obvious, but quite true.... i didn't
look at your earlier paper, but if anything has indegree 2 or
outdegree 2 you're dead, and otherwise if all have in and out degree
1, just start anywhere, around, and see if you touch them all before
you get back. one's mileage may differ for 0-node and 1-node graphs.)

but then you cite an IPL paper from the 1970s as saying that this case
is known to be NP-complete (even for planar graphs). and so you
conclude P=NP.

and then in the current paper you, having already proven P=NP earlier,
discusses if we can test whether a Ham. cycle exists (for the degree
at most two case) faster than your alg. for finding a cycle.

i don't have the IPL paper but i'll bet it doesn't prove what you say
it does. i'll bet it proves something else.... maybe that for graphs
where for each node the indegree is at most 2 and the outdegree is at
most 2, then (even for the planar case) Ham. cycle is NP-complete.
that is, i'd guess your def. of degree of a digraph differs from that
of the 1970s paper. this would totally destroy your claim of having
proved that P=NP. just a guess---i'm in germany and so blind to my
school's library, and any or all of these comments may be wrong.

aha... i see another paper that describes plesnik... plesnik seems to
be about graphs with ***OUTDEGREE*** limited to 2. so it does not
prove what you claim it does.

anyway, below is my standard warning letter. all the best to you. "

It is confuse me by the grammar in his letter, " graphs
***OUTDEGREE*** limited to 2 ", what is different with digraphs
with degree bound two?

I had reply the email and asked he show me where is "the paper
describes plesnik" and what is the title?

Maybe some one in here could help me understand what he comments.
Thanks very much!

Best regards,
Guohun Zhu


He is claiming that Plesnik's proof is for planar graphs in which each
vertex has at most 2 outgoing edges, but arbitrarily many incoming
edges. I haven't been able to track down Plesnik's paper, so I don't
know whether this is the case. Plesnik's title is ambiguous in this regard.

The person writing this letter has obviously misunderstood your earlier
paper, as it deals with digraphs with up to 2 incoming edges and up to 2
outgoing edges - not a total of at most 2 incoming + outgoing, as he
states. However, if his description of Plesnik's result is correct, it
breaks your proof that P=NP, as you clearly limit the indegree of each
node to 2.

Rod Howell
Associate Professor
Dept. of Computing and Information Sciences
Kansas State University
http://people.cis.ksu.edu/~rhowell/
.

Relevant Pages