[FOM] [1305.5976] A Polynomial Time Algorithm for the Hamilton Circuit Problem

[Tony Beta Lambda]

Sorry for the long post.  You can skip the ``background'' part.

I'd like to add some background:

Here, in mainland China, it is a fashion that electronic engineers
``solve'' various graph problems that are well-known to be intractable with
their ``algorithms'', most of which being described by a fancy language but
turns out to be simple DP or linear algebra, and claim it to be correct.
 As far as I know, all of them contain some obvious flaws.

I personally was a member of an undergrad (yes I am an undergrad) group
with absolutely no knowledge in graph theory, not even knowing what DFS or
BFS is, (they major in EE while I major in math) trying to solve graph
isomorphism problem.  Their ``algorithm'' is stated with many EE
terminologies (exciting current, resistivity, etc.) but is essentially
finding the smallest eigenvalue of the adjacency and associated
eigenvector, then finding a permutation between them.  You may search
``graph isomorphism Shang Huiliang'' to find their papers.  Sorry I cannot
give a link because Google Scholar is not working here.

A brief summary about the paper:

This paper proposed an algorithm for ``Multistage graph simple path''
problem, which features a directed multistage graph, with each vertex
equipped with a set of permissible edges (cf. Definition 1, 2).  The
problem is to determine if their is a path consisting entirely of
permissible edges, which, from my point of view, is no different from *testing
reachability* in the permissible subgraph.  The author invented tons of
fancy words but can never hide that fact.  The algorithm seems right (after
all, it is difficult to find an incorrect algorithm for a problem simple as
reachability), but surely *HC cannot be reduced to it*!  To be specific,
the construction preceding Theorem 4 is unclear and Theorem 4 is wrong;
 the so-defined ``simplicity'' of path does *not* imply the vertices are
mutually distinct.

The tests done all focus on the correctness of the algorithm itself, hence
all the positive results;  but seems no one has tested the reduction
algorithm, which is totally wrong.

It is my first time to post on FOM (and a fairly long post), so please
point out if I am not following the etiquette.


On Thu, May 30, 2013 at 7:57 AM, // ravi <ravi-lists at g8o.net> wrote:

>
>
> I haven’t seen this appear on the list, so:
>
> http://arxiv.org/abs/1305.5976
>
> > A Polynomial Time Algorithm for the Hamilton Circuit Problem
> >
> > Xinwen Jiang
> > (Submitted on 26 May 2013)
> > In this paper, we introduce a so-called Multistage graph Simple Path
> (MSP) problem and show that the Hamilton Circuit (HC) problem can be
> polynomially reducible to the MSP problem. To solve the MSP problem, we
> propose a polynomial algorithm and prove its NP-completeness. Our result
> implies NP=P.
>
>
>         —ravi
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>



-- 
*Tony Beta Lambda*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130601/3924c03b/attachment.html>