I haven't looked at your algorithm in details, but I see you describe that the algorithm runs in O(n^7), polynomial time. So are you saying that you have solved a NP-complete problem in a polynomial time? If the answer is yes, I doubt its validity. Or the algorithm is just a heuristic method, which does not guarantee the correct answer for all the cases.

Let me see the source code as well.

I works in the field of Bioinformaics and DNA computing. I am interested in this problem because we need a fast algorithm to solve large TSP problem for big data analysis in bioinformaics. Also, I have been publised papers on using DNA computing to conqer the NP-complete 3-SAT problems.

I have been discussing with Lizhi Du on his great algorithm for more than 4 years on a Chinese website (http://blog.sciencenet.cn).  I understand his algorithm quite well. It is really a pitty that his algrithm could not get published or applied to solve problem.  If you have any question on his algorithm, I can help to answer your questions, or translate Lizhi's answer. 

His windows program does works pretty well on the hard HCP problems on the TSPLIB (http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/). It takes only about 1~2 sec to solve a 1000-node hard HCP problem. Unfortunately, however, he refused to provide the source code. I even wrote a program by myself according to his paper, but my program does not work as well as his. I have to do all possible inserts and cuts to find the H cycle, so it is much slower than his. His own program is very fast. He said his program is much more complicated than mine.

I believe that his algorithm is indeed a polynomial one, because the time complexity is polynomial even if you do all possible inserts and cuts. But I am not sure whether or not it will always succeced without any fail, as I do not fully undertand his proof. His algorithm is hard, and his proof is even more difficult to understand. I also helped him to edit his paper, which was even more difficult to understand before.

Hi, Dear Peter T Breuer,

I don't know what the step that I did not follow is. If I know, I would have followed.

 My program is quite simple. I just follow the main steps of his article:

 (1) To generate n(n-1)/2 random "broad cycles", each contains a fixed pair of nodes (he called the "main pair" );

 (2) To cut and insert at a location to generate new broad cycles which have lesser breaks, while keeping the main pair not changed.

 (3) repeat (2) until a H cycle is got (which have no break), or stop at a maximum number of iterations.

 According to his analysis, the time complexity is O(n^7). I thought the time complexity is indeed polynomial, but the O(n^7) computation time would be too long when the problem size is large. His program is fast, he must use some secret tricks which greatly accelerate the process. I also find some tricks that can greatly accelerate the process. But I don't know what tricks he used. 

 However, the biggest problem is that I don't understand why the process is guaranteed to find the H cycle if they exist. I don't fully understand his proof, but I strongly felt that he is probably right, as I find his algorithm is in principle very similar to DNA computing algorithms, which is naturally highly efficient. Otherwise I won’t waste my time to follow his algorithm. Basically, he proves his algorithm in three ways:

 (1) test his algorithm on all possible graphs for n

Algorithms are never recognised without their details exposed.  There is no *secret trick* in software; pure determinism.  So, you can either explain in detail exactly how the algorithm works (no hand-waving, like *he proves his algorithm in three ways* as nobody is going to buy such vacuous argumentation), or you have nothing to offer.

You don't have to cut and insert at every location.In my program, I used a trick which can decrease the number of breaks fastly. 

For every break, I find two nodes (say v1 and v2) that was connected, and flanking the current break, cut the segment (the nodes) between v1 and v2, and insert the segment into another location of the borad cycle, where can decrease the number of breaks.

I called this tricky as "merging of subpaths", as the two partial paths flanking the break is merged. For the TSPLIB HCP problems, the running time is:

n=1000 2sec

n=2000 20 sec

n=5000 4min

This very simple tricky is really efficient, but I still have two problems:

(1) I don't know why it is efficient.

(2) Some times it fails.

If I cut and insert at every possible location, the H cycle can be found anyway, but it takes too long time.

Lizhi Du, the author provided some hard graphs which fails my program, but his own program is fast and never fails. I thind he might alsoinclude the above "merging of subpaths", but he might have some additional tricks he do not want to reveal at this moment.

I told him that he wil have to publish his code if he want his algorithm recognised, otherwise the other people will not recognize his algorithm. He is still thinking about when to release the source code. I think the reason why he keep the source code unrevealled is because that he is afraid of losing control of his program. He might have been putting tremendous time and efforts on his algorithm. I understand that the program is his treasure, his child, and his life, he won't give it away easily.

However, if he is right, it means P=NP, it will become a treasure (or evil?) of mankind.

One more time.  Mr. Wang, you can either explicitly, in detail and with no uncertainly (programs are after all purely deterministic things) provide proof, or you have nothing to offer.  Either supply sufficient detail that your claims can be verified or stop bothering us.

Hi Peter,

 I am sorry my last statement is not clear. I read your previous answers to Lizhi Du, I thought you know what is broad cycle, what is cut and insert, and what is break. But it seems that you don't. Then I have to explain them firstly:

(1) A broad cycle is a complete path with breaks, the n vertices were laid side by side to form a cycle: X1X2X3...Xn, where Xi is the n vertices, or abcdefghijkm…., where a, b, c, d, … is the name of the vertices.

(2) A break is the status of two neighboring vertices that were not connected. An edge is denoted by nothing, while a break is denoted by a star (*). A broad cycle with zero breaks is a Hamilton cycle.

Then let me answer your above questions:

What is a "location" and how is it selected? (I presume this is a vertex).

[Yes, a location is a vertex in a broad cycle.]

What is a "cut", and what is an "insert"? (I presume a "cut" is the removal of an edge from a path in the "broad cycle". I presume an "insert" is the addition of an edge to the set of paths in the "broad cycle").

[No, cut and insert is the operation of moving and rearrangement of the nodes, not the edges.]

How are the "cut" and "insert" selected? (Is it to reduce a measure of badness on the "broad cycle", such as the number of distinct paths in it, or the lack of length wrt the maximum possible of the longest path in it?)

[The cut is selected by the breaks and the edges, and the insert is selected by counting the number of breaks.]

 For example:

Given a 20-node graph, a broad cycle abcdefg*hijklmn*opqr*st is a complete path, in which ab, bc, cd, ef, de, ef, fg, gh, hi, ij, jk, kl, …, are all connected, but g*h, n*o and r*s are not (the broad cycle contains three breaks);

 For break g*h, find two nodes (say c and m) that was connected, and their neighbors, b and n are connected to g and h, (say bg and hn), cut the segment cdefg, and insert them inversely between b…h, the resulting broad cycle is abgfedc*hijklmn*opqr*st, and then cut the segment hijklm and insert it inversely between c…n, the resulting broad cycle is abgfedcnmlkjih*opqr*st, where the number of breaks decreases by one.

 This is just one of the tricks I used in the program, but it is surprisingly efficient, and greatly accelerates the computation, although sometimes it fails. Lizhi Du must use a lot more tricks than I did.

 I have asked Dr. Lizhi Du for his permission to post my program here. If I got his permission, I will post my program together with the source code here later.

Dear Mr. William R. Buckley,

You know that this is Lizhi Du's question.  Because Lizhi is not good at English, I saw a lot of misunderstanding in previous answers. I asked him whether he want my paticipation in this discussion and helping him to answer questions, and he said yes. I am here just want to help Lizhi to communicate with people who want to know more about his algorithm. I am not fully understood his algorithm, but Lizhi can answer the questions in Chinese, and then I can translate his answer into English.

I am terriblely sorry if I bothered you. If so, would you please just ignore my answers?

I

Yes, a "broad cycle" is a "Hamiltonian circuit minus a few or any number of (non-adjacent) edges".

Why do we have a Hamiltonian circuit in at most something like dp tries? You can try all the edges at one end of each path, because the broad cycle is a cycle, so there is no end at all.

So it appears that the problem is getting hold of a "broad path" with at most a certain fixed number of path components, say "7".  [what do you mean?]

Please see above post for a figure on how to perform a cut and insert.

【Thank you for the diagram, and your patiency.】

You have reduced the problem of building a hamiltonian cycle in polynomial time to the problem of building a "broad cycle" with at most a certain fixed number of component paths (say "7") in polynomial time.

【Do you mean you somewhat agree that this is probably a true polynomial algorithm? Please be aware that this is Lizhi Du's work, not mine. I am speaking for him. Just like you, I am interested in this problem and curious on whether this is a true polynomial algorithm.】

Because there are p paths in the "broad cycle".

So the number of paths in the "broad cycle" is reduced by one.

【I would say that only one "virtual path" is represented by each broad cycle. In fact, you don't have to care how many paths are there in the broad cycle, you just count the number of breaks instead. The path may contains one or more breaks (missing edges), if the path has no break, it is Hamiltonian. If it contains two or more breaks, actually it contains two or more subpaths. Like you have said in the above post: a broad cycle is a set of subpaths in the graph that do not intersect and which jointly cover all the nodes in the graph.】

because the broad cycle is a cycle, so there is no end at all." makes no sense to me. The "end" of the broad cycle is not being discussed.

【The broad cycle is a circular construction, so there is no end at all, for example, in your diagram, ABC*DEF = DEFABC* = BC*DEFA =...， you don't care where the path starts and ends.】

But you require the path to stop precisely at C. So the situation I have drawn is more general.

【No, we do not require the path to stop precisely at C, because the initial path is generated randomly. The above figure is showing just one of the possible broad cycles on how to perform a cut and insert to reduce the number of breaks. 】

However I see no requirement that CD should exist in the graph there is a "break" from C to D. I do not see that the construction requires that at all.

【No, we do not require CD should exist in the broad cycle, it only shows if C*D is a break, how to remove the break.】

Yet it is a condition for the "broad cycle" to be such there must be breaks between its paths). I have to ask why one would do this transformation since it suffices to just add the missing edge CD to obtain the same effect. Why bother?

【No, you don't have to include breaks between its paths, if the initial path happened to have no break, it is already a H cycle, the computation ends.】

【But, the randomly generated initial broad cycles usually contains many breaks, so you will have to perform such kind of cuts and inserts on these "broad cycles", the number of initial paths is count up to m*m*n(n-1)/2, where m is the average degree of the graph, n the number of vertices. 】

【For each broad cycle, when you got a new broad cycle which have lesser number of breaks, the old broad cycle is just abondaned, so the number of broad cycles is not increasing exponentially, but kept unchanged, in the computation process.】

In the more general situation that I have drawn, the transformation must introduce another path or two, covering the "tails" in the middle bottom of the diagram, hypthetically extending from C and D. Why would one always find a situation such as you have drawn, rather than the more general one that I have drawn? It seems to me that the mechanism that makes this often work is that the paths are internally reordered by the basic transformation, which offers up many future possibilities. If one were to do the obvious and just add CD, no reordering would result.

【In the above, I just show one of the possible cuts and inserts to reduce the number of breaks. There are still many other ways. But I found this one is the most efficient. 】

【Sometimes it does fails. In this situation, you will have to try all possible cuts and inserts (including those does not change the number of breaks) to find the H cycle, so the worst case complexity is O(n^7). But usually the computation is finished quickly in O(n^3) time. 】

Thank you!

Is that not so? Do you mean instead by C*D that CD does not exist in the graph?

[ Yes, C*D mean CD does not exist in the graph. ]

[I think all of your misunderstanding comes from here. Please reconsider, and see what problem do you still have.]

a list of those configurations and the transforms that treat them.

[I don't know all the configurations and the transforms that treat them, I will help Lizhi to list them in his paper.]

What proof is offered that this or one of the other configurations must arise? Is there any? The following seems to say no:

Sometimes it does fails. In this situation, you will have to try all possible cuts and inserts (including those does not change the number of breaks) to find the H cycle, so the worst case complexity is O(n^7).

[I mean that this technique works the best but sometimes it fails. There are many other techniques works well too, when they works together, they will never fails.]

I don't know why you think O(n^7), but "try all possible cuts and inserts" is exponential search, in principle (and I still don't know what "cuts and inserts" means ... perhaps you mean "one of the other transforms"). 

[There are n^2 initial broad cycles, generated for each main node pair. "try all possible cuts and inserts" on these n^2 initial broad cycles, each has n^2 possible location for cuts, and n possible location for inserts,  and each broad cycle may be updated for n times, and a cut and insert need O(n) time. So, the worst case time complexity is n^2×n^2×n×n×O(n)= O(n^7). ]

[I am still completely unclear on what "cut and insert" means, hence cannot verify why you think that there are "n2 possible location for cuts, and n possible location for inserts" - however, for each possibility you need to check that each or any of the transforms you have available is feasible, which takes extra time that needs accounting too.]

ABCDEF is a broad cycle,

Possible cuts: AB， ABC ABCD, ABCDE, BC, BCD, BCDE, CD, CDE, DE

Possible inserts: A^B, B^C, C^D, D^E, E^F, F^A

I think, is that it takes On7 operations at most to discover that you cannot find a hamiltonian circuit this way, but that you believe the situation will never arise. What leads you to strongly believe that? Experience?

[Lizhi said he proved that this process can find H cycle in On7 operations, but I myself do not understand his proof completely.]

In principle, your complexity estimate leads to a way of generating a counter example automatically, with a little more attention to the value of the constant of proportonality in the On7. Or it will turn out to be a proof if the automated counter example construction fails ... but I doubt that.

[I doubt too. I do see his algorithm is efficient in most cases, but I am not sure whether it is completely sucessful in all graphs. ]

Dear Mr Lizhi Du and Mr Xiaolong Wang,

I downloaded your attached C++ application, launched it and then entered the collection of edges of the simple graph (see the attached image). Your application found a Hamiltonian Path, but not the Cycle!

I can attach my input file and the output file if you are interested.

Sincerely yours, Alexander

Dear Mr. Alexander,

I am not a author of this article. Like you, I am just a reader. I was interested in this problem. Your question can only be answered by the author Lizhi DU by himself.

Xiaolong Wang

Dear Mr. Alexander,

Yes, this program is for getting a hamilton path from vertex 0 to vertex n-1. A cycle is easily got based on this technique.

thanks to Mr. Wang.

Lizhi Du

Dear Mr Lizhi Du and Mr Xiaolong Wang,

Me and my student Ivan Fedorov succeeded in implementing your wonderful algorithm! It was not an easy task regardless of the fact that you tried to make it very clear.

I really think that you and your work deserve the world's recognition and the Clay Mathematics Institute Prize. Here is one of the shocking results. We compared Roberts & Flores Backtracking algorithm and your algorithm (we now call it Lizhi Du algorithm) while solving Knight's tour problem (https://en.wikipedia.org/wiki/Knight%27s_tour).

• Roberts & Flores Backtracking algorithm - over 780 millions steps (computer boiled for several hours).
• Lizhi Du algorithm - 234 steps !!! We could not believe our eyes!

Our implementation uses C# and (controlled by the user) visual animation to clearly show what is going on (how the algorithm selects and deselects graph edges). If you want to see our results, please write me a private email ([email protected]). 

We are going to publish an article on codeproject.com and we will certainly praise your great work.

Thank you very much.

congratulations, Dr. LIizhi DU!

Thanks to Dr. Xiaolong Wang! 

Dear Prof. Alexander Chernosvitov :

Thank you very much!

My English expression is not good, my paper is not good writing. I need help.

Thank you very much!

Hi, every friend and expert, I just asked a new question including .exe and paper download, Thank you for your attention