1. The Method of How to Control One's Fortune

1-1. Why Did We Begin Hamiltonian Circuit Problem ?


Hamiltonian Circuit Problem is a problem on graphs formalized by Sir William Rowan Hamilton who is a mathematician of 19th century in Ireland and it inquires "whether there is a circuit passing all the points of given graph or not".

In the case of a graph whose number of points is N, the number of such circuits is N! at most. The simplest way to examine whether there is a circuit satisfying the request is to check all the paths thoroughly in round robin and its calculation cost amounts to the order N! of exponential time algorithms. It is the question whether it is able to get the solution with more efficient method of polynomial time algorithms than that. Thus there is a group of problems which is not certified if any polynomial time algorithms exists or not and they are called NP (non-deterministic polynomial) complete problems. NP complete problems have a characteristic that they are able to be transformed mutually to other problem in polynomial time. Therefore when one NP complete problem is solved it is equal that all other problems get their solution.

This problem has rejected challengers of so many mathematicians for the long time of 1 century. It is suitable to say that it was such as the Shining Princess who had refused any of their proposal. As Hamiltonian Circuit Problem was a well known problem (that was a woman in rumor), it might be no exaggeration to say that her proposers have included most of famous mathematicians.

The first aim for starting this study was to give some theoretical assurance to our programming techniques called N-tree or nodule list which we developed to operate graphs. When the author had joined Japan Society for Software Science and Technology his motivation was originally that he had wanted someone to accomplish a theoretical construction of graph operations with regard to some programming practice. But the time had passed doing nothing in excuse of busy, and one day he became aware unintentionally that he had begun it by himself.

At first, the goal was to set the Graph Theory algebraic. For that purpose we invented a method to assign numbers called Babbage number to any points of a graph. As this method seems rather promising, we applied it to solve graph isomorphic correspondence problem. We defined a weighted tree having Babbage Numbers on each points based upon our accustomed N-tree, and we thought that it would be able to compare two graphs each other after transforming canonically if the weighted tree could be transformed to some canonical tree. We tried with rather difficulty and formalized the method somehow.

On the way, we challenged the Hamiltonian Circuit Problem. When we solved the problem with a hand-writing method, it was understood that the problem was merely an applied question of the graph isomorphic correspondence problem. We became aware that it was all right to straighten a N-tree or to transform it to be an isomorphic graph which comprised only series branches. Actually tried on paper, it had been solved in 2-30 minutes almost in a moment.

But as it was quite mysterious why was it solved so easily, we returned to the graph isomorphic correspondence problem and intended to inquire into our solution. When a complete graph was given as an exercise for the isomorphic correspondence problem, it ruined for a moment. Gradually we came to know that this deficit was extremely difficult to be covered. Certainly if we withdrew around there, we did not get involved so deeply. However, it already came to be an interesting affair "to think about graph problems".

We discontinued the graph isomorphic correspondence problem for the time, and decided to concentrate upon the Hamiltonian Circuit Problem. The method of "algebraic Graph Theory" was very attractive for us but it had a defect that the numbers treated in the method became enormously big and the method did not seem easily to converge, then we returned to the classic method of graph theory called combinatorial method for our consideration.

We devised and tried at least 10 kinds of rapid solutions with respect to such small scale problems that could be solved drawing simple diagrams on paper. Some of them gave us sufficient answers but the some rather bogus were included. At that time, our solution had already evolved into such degree that 12 points non-planar graph could be solved in several stages. Concerning that to examine all branches of 12 points complete graph thoroughly made 479,001,600 cases, we thought that it might be a good enough record.

However, since there were no other way to judge a non-Hamiltonian graph than to examine thoroughly with respect to all the cases, it seemed by no means inevitable that calculation cost came over exponential time. We understood that on the assumption that "to select contradictory branch in an arbitrary selection phase necessarily causes a deadlock in the phase", the calculation could be ended in the cost of O(N^4). Such graph did not really exist but concerning an ideal graph on which such assumption was true, the skeleton of the problem gradually came to be visible.

Moreover, we understood that if a graph had a topological characteristic of strongly-Hamiltonial, the problem should be solved completely. Strongly-Hamiltonial is a peculiarity that while every point of a graph has three or more branches the graph does not deadlock, and it seems certainly true in operating and observing a graph, but a fictitious characteristic actually never exists.

We decided to study using bipartite graphs since the N-tree was not applied well for the combinatorial method. We observed fully the phenomenon called deadlock which occurs on the selection of incorrect path and it came visible by degrees that this phenomenon has a non-deterministic characteristic and the most of the difficulties of the Hamiltonian Circuit Problem regard this non-determinability. Deadlocks occur simultaneously and concurrently at plural places and the places are essentially non-determinable.

We named such non-determinability that appears in the Hamiltonian Circuit Problem Omega-Problem. That is, there is Omega-Problem in the Hamiltonian Circuit Problem and if this problem would not be solved then any solution was revealed sooner or later as a temporizing one. It is inevitable for the calculation cost to be NP order if the algorithms includes this Omega. Omega is a dragon squatting before the princess who is imprisoned in the depth of cavern.

On the stage when a clear graph scheme of experimental graph was formalized, the problem was transformed into rather easy form to be treated. Moreover, we obtained a Hamiltonial homeomorphic graph called short-circuit graph progressed one more step from experimental graph. The method of short-circuit graph is based on the theory that "a graph obtained by short-circuit and reduction of paths included in a part of a Hamiltonian tie of a Hamiltonian graph is a Hamiltonian graph", and we succeeded in giving proofs to the theorems with respect to the short-circuit graph which method gave our Hamiltonian experimentation an confirmed and solid immobile point.

For small scale problems, the short-circuit graph method is surely a strong method. However, it gradually appeared that this method was so weak as objected graphs grew into large scale. With the short-circuit graph method, a branch is assumed to be a branch of Hamiltonian tie and determined by reducing the graph step by step to converge the problem, but when a 10,000 points graph is experimented by this method there continues a stupid situation where no event happens on selecting incorrect branch toward 9,990 steps. Moreover, to correct a mistake found out at this last phase all points have to be expanded through these all phases in the depth of the ocean.

To improve such situation, a method of k-terminal graph division was introduced at first. This method is a method dividing a graph into both of left and right graph completely, experimenting each graph independently and confronting their determinative paths each other. If this method was able to be applied in any moment, of course the Hamiltonian Circuit Problem could be solved easily. And further, such constraint that terminal points require even number of IO gives sufficient effect to restrict the problem. However, k-terminal division method has three difficulties as below.

Giving up examining every terminal division, such restriction that only i.e. 2 or 3 terminal divisions should be examined came from practical compromise but it was bitter selection to use a riddle of big mesh.

Cut-set division was introduced as a method similar to the k-terminal points graph division. The principal of the cut-set division is almost the same with k-terminal division, but it divides a graph without conforming to points but removing plural branches. Although cut-set division and k-terminal division are very close, it is better to use both method for it is probable that some contradiction might leak with one method and be detected by another method. It is obviously true that in the case of cut-set division, to make a perfect experiment is impossible by reason of costs as is in the k-terminal division.