Hamiltonian Circuit Experiment Program
(C)Copyright June 6, 2000 Baba Laboratory Co., Ltd.
Japanese
edition
|
|
Ariadne100 Hamiltonian Circuit Experiment Program (C)Copyright June 6, 2000 Baba Laboratory Co., Ltd. |
Japanese edition |
 |
 At present, the Hamiltonian Circuit Problem has had an offer of one million
dollars. This is a part of the prize money totally $7 million which Clay Mathematics Institute
promised to those who solve the seven problems unsolved at the end of 20th century. The
top of it is the NP-Complete Problem, and to solve "Hamiltonian Circuit Problem"
is equal to solve it. Hamiltonian Circuit Problem is a problem to judge whether a graph
has a hamiltonian cycle (a cycle which passes all points of the graph) or not. The way to
solve the problem efficiently (in polynomial time) is unknown for the present. |
Sadly Ariadne was defeated on the first debut match. She was knocked out easily at a MIS punch given by Stanislav for a minute while unknown whether a gong of the first round was going on or ceased. However, as SAT01 of Stanislav is slightly behind Ariadne at hajo graph, both sides recognize that the two programs are nearly equal in real power. As we have a secret plan to overcome the MIS punch, it is able to strengthen Ariadne, but we decided to come again after decreasing the weight. The ring name of the second challenger to be sent is "Gordian Knot".
Ariadne100 rev1.3k release
8.23.2000
Download Hamiltonian Circuit Experiment Program 153KB
What is updated at the latest revision? (rev1.3k 8.23.2000) |
 |
 |
The following functions are added to the newest version of Ariadne. It has awakened so many responses since the first version of Ariadne was published on June 6th, 2000. Especially discussions exchanged at the mailing list "Theory Edge" are reflected on this update.
Supplement of k-Regular
graph samples and abolishment of complete graph samples
This outputs k-regular directed/undirected random sample graphs. The complete graph sample menu was deleted. A complete graph can be output with k-regular random graph by assigning (graph's vertices number - 1) for k. This addition of the function owes to the advise of Dan Pehoushek. He appointed that k-regular graphs are almost hamiltonian when k is greater than some number and it is very probable that the some number is 3, and strongly recommended to test such type of graphs. ("3-Regular graphs are almost hamiltonian" means "almost graphs are hamiltonian".)
This displays the graph's entropy (in natural logarithm, every logarithm used in the program is all natural logarithm) at experimental result lines. It indicates the "information amount" of the information at the time when determined "the graph is hamiltonian" or "it is not". Vladimir Nuri spoke at above mailing list "If you say that NP-complete problem is solvable in polynomial time, it is equivalent to saying that perpetual motion machine is realizable.". What the second law of thermodynamics and NP-complete problem have to do with?
Addition of file convert
function
This function converts a sample graph file into CNF(Conjunctive Normal Form) DIMACS format file. There are 2 kinds of the conversion. See Mutual Transformation of NP-complete problems.
HCP->SAT conversion algorithm was developed by the help of Stanislav Busygin.
We decided to abandon Readme text file so far and to use HTML file. Even in the
contents, pages are increased and the composition is arranged. Especially the articles of
"Usages of Ariadne100" and "Regarding Complexity" are retouched. I would be grateful
to hear your opinion 
about the abolition of Readme text file.
A device is built-in to avoid someone being a stray child in hyper-texts. There is a hidden link to the upper node ever at the tail of a heading of a node diverged from an upper node, and you can return back to the upper node at anytime. Try and click at the right of "Update of the manual" above.
Usages of Ariadne100 |
|
|
The following headings are explained.
< How to install >
SetupAriadne.exe is a self-defrost-archive file. Move the file to an appropriate folder and double-click it, then the installation completes. There expanded Ariadne100.exe and other several files in the folder. Ariadne.html is both of a manual and a document with the same contents of this page you read now. The other files are its attached files.
< When you Start >
(1)Start a MS-DOS prompt program.
(2)Move to the directory where Ariadne100.exe exists.
(3)Execute the Ariadne100.exe at the MS-DOS command line.
When you start Ariadne100.exe, succeeding title lines, a menu to be described at the next section is displayed. Enter keys following the explanation on your screen.
< When you end >
At first return to the menu stage and select "Quit"
menu entering a numeral 0, then it ends the program. At the case when you need to force to
stop in such as an automatic experiment mode,
please press CTRL+C keys. Press PAUSE key to stop scroll. besides you can resume the
scroll by ESC key.
At the initial stage, the following menu is displayed. You can choice a sample graph type among the menus. Most of samples are automatically generated by each sample generation algorithm but you can test arbitrary handmade graphs at 8.Read File.
1. Automatic experiment
2. Random graph
3. Mesh graph
4. Peterson graph
5. Hajo graph
6. Diamond graph
7. Polyhedron graph
8. Read File
9. Convert File
0. Quit
In automatic experiment mode, it generates sample graphs automatically and carries out automatic experiments continuously. The following 8 kinds of automatic experiments are supported. It remembers the parameters lastly applied and generates samples by the setup. In automatic experiment mode, all of samples is always shuffled once. Accordingly if the setup is the same, the labeling of a sample graph comes every time different.
----------------------------------------------------------------------------------------
| graphs | H/NH | parameter | samples |
----------------------------------------------------------------------------------------
| 1. Auto random graphs | H/NH | last accessed type | any |
| 2. Mesh graph series | H/NH | last accessed type | 100, 16 |
| 3. Peterson graph series | H/NH | 150 | |
| 4. Hajo graph series | H/NH | last accessed type | by parameters |
| 5. Diamond graph series | N | last parameters | by parameters |
| 6. Polyhedron graph series | H | 5 | |
| 7. Graph file names list | H/NH | ant | |
| 8. Hamiltonian world tour | H/NH | last parameters | about 400 |
| 0. Quit |
This generates random sample graphs using the parameters lastly applied. This experimentation will continue (for any days) until it is forced to stop by CTRL+C key or else. Around 1000 samples will be tested in 24 hours. In the case when some especially hard problem has occurred, it pauses and asks you whether continue the experiment or not. Frequency of occurrences of such hard problem is about one per day. Experimental results are all recorded in the auto experiment log file(Ariadne.log) automatically. This log file is kept until the next auto random graphs experimentation. See 2.Random graph.
In the case that the last experiment was planar mesh graph, this performs continuous auto experiments of 100 mesh graph samples from 1*1 to 10*10. In the case of N-th dimension mesh graph, it automatically generates 16 mesh graph samples from square to 6th dimension. See 3.Mesh graph.
This generates totally 160 samples of cycle size 2 to 50, altering steps number. See 4.Peterson graph.
This carries out an auto experimentation using the parameter of the last experiment. The number of sample graphs to be generated is due to the set of the parameters. Hajo graph includes very hard graphs. In such case, a panel appears and asks you whether continue the experiment or not. See 5.Hajo graph.
This carries out an auto experimentation using the parameter of the last experiment. The number of sample graphs to be generated is due to the set of the parameters. Graphs of this type are all non-hamiltonian. See 6.Diamond graph.
This makes auto experiments of 5 kinds of polyhedron graphs. All this type graphs are hamiltonian. See 7.Polyhedron graph.
This automatically executes graph files enumerated in a file-name-list. If the file does not exist, the file name is ignored. The file-name-list file and graph files must be on the same directory of Ariadne.exe or the names must be described in full-path name. In the file-name-list, describe one graph file name (or full path name of the file) per line. See 8.Read File.
This continuously carries out auto-demonstrations above 1-2 to 1-6. Although the required time may alter by the setup, about 400 sample graphs are experimented in about one hour.
This stops the treatment and returns to the menu stage.
A random sample graph of the following 6 kinds is generated using random numbers. You can make a complete graph from k-regular graph.
1. undirected graph
2. undirected hamiltonian graph
3. undirected k-regular graph
4. directed graph
5. directed hamiltonian graph
6. directed k-regular graph
Designate graph size and minimum edges number for 1,2,4,5. It adjusts so that about 5 % vertices has the minimum number. A k-regular graph is generated in 3(6). k-Regular graph is a graph, all of which vertex has same edges number k. 2 and 5 graphs are always hamiltonian but the other results are not certain. A complete graph is generated by designating k=(graph size - 1) in 3(6) k-regular graph.
When you find out a sample which Ariadne cannot solve in an automatic experiment (or
other cases), it would be greatly appreciated, if you send a to the author,
attaching the log file.
This generates a regular graph like mesh of a Go-board. Every sample generated is always shuffled once. There are following 2 kinds.
1. Square(planar) mesh graph
2. N-th dimension mesh graph
In both cases, if the vertices number of the graph is odd, the graph is definitely non-hamiltonian. If the number is even, it surely has a hamiltonian circuit. For more about mesh graph, refer to "Mesh-diagram Experiment".
Peterson graph is a famous non-hamiltonian graph of vertices number 10. This generates a sample graph modified from it. Original peterson graph consists of two cycles of 5 vertices and the cycles are connected by edges twisted by 2 steps. Designate cycle size and the steps number for twisting. A graph generated becomes either non-hamiltonian or hamiltonian.
Hajo graph is the toughest non-hamiltonian graph ever known at present. A sample graph of the following 4 kinds is generated and modified on the base of the original graph. Every sample generated is always shuffled once. See Mutual transformation of NP-Complete problems.
1. original hajo graph
2. hajo+1 graph (hamiltonian)
3. super hajo graph
4. ultra hajo graph
This is the graph which turns to the counter example refuted Chvatal's conjecture of "Every 2 or more tough graph is hamiltonian". It consists of v * (8 vertices graph) and a u vertices complete graph, and if v>=2*u+1, it becomes a non-hamiltonian graph. Hajo graphs of u>1 are very hard graphs. Perhaps it takes one year to try solving the 42 vertices hajo graph of u=2, v=5 by Ariadne. (The 8 vertices subgraphs inside hajo graph is a "diamond figure" in our terminology.)
Adding an edge to a hajo graph necessarily makes the graph hamiltonian. Peterson graph also has this characteristic. Accordingly all graphs of this type are hamiltonian. Although merely one edge is added, Ariadne easily detects that the graph turns to a hamiltonian graph.
Hajo graph is a hard enough graph and yet this is a heavier graph added a complete graph. The additional complete graph is connected to the fixed two vertices of original hajo graph. If the original hajo graph is non-hamiltonian, this graph is also a non-hamiltonian graph.
Similarly to the 5-3 super hajo graph, this is a heavier graph added a complete graph. The additional complete graph is connected to the clique(complete subgraph) inside original hajo graph. If the original hajo graph is non-hamiltonian, this graph is also a non-hamiltonian graph.
This is a non-hamiltonian graph consists of an even vertices cycle and a complete graph. Two graphs are connected by stitching in odd steps. An even vertices cycle is the simplest "diamond figure".
This generates the following 5 regular polyhedron graphs.
1. Tetrahedron
2. Hexahedron
3. Octahedron
4. Dodecahedron
5. Icosahedron
These graphs are all hamiltonian. Especially 4. Dodecahedron is the original title presented by Sir. Hamilton who recognized first the Hamiltonian Circuit Problem. He called this a "journey round the world" visiting all cities correspond to each vertex of a regular dodecahedron.
You can read an arbitrary sample graph stored in a file and experiment it. The format of sample graph is very simple as is explained at the next section. The graph file must be in the same directory of Ariadne100.exe or must be indicated by full path name. An arbitrarily stored experiment log file, an analysis log file or the data stored into auto experiment log file in an auto experiment is able to be re-experimented directly as a graph file.
This converts a sample graph file into CNF(Conjunctive Normal Form) DIMACS format file. Select a conversion method from the following menu. Please refer to The Second DIMACS Challenge for the DIMACS CNF file format. See Mutual transformation of NP-complete problems.
1. 2-Factor problem to CNF
2. Hamiltonian circuit problem to CNF
This transforms sample graph data to a 2-factor recognizing problem in CNF format. If the graph has a 2-factor, the logical formula is satisfiable. Designate input file name and output file name respectively. If these files are not in the same directory of Ariadne100.exe, you must designate the full path name. Data size will be augmented by N^3 order after this transformation. Polynomial time algorithms are known for 2-factor problem.
This transforms sample graph data to a hamiltonian circuit problem in CNF format. If the graph has a hamiltonian circuit, the logical formula is satisfiable. Designate input file name and output file name respectively. If these files are not in the same directory of Ariadne100.exe, you must designate the full path name. Data size will be augmented by N^3 order after this transformation.
This ends the experimentation.
Please refer to the next chapter "Timing Chart Method"
for more detailed movement of Ariadne.
The program can read an arbitrary text file as a sample graph data file in such format as below. All of log files saved in an experiment can be re-experimented as a sample graph afterward.
#outgoing vertex number > sequence of incoming vertex numbers
--Example--
#1 > 2 3
#2 > 3 5 6
#3 > 1 2 4
:
Only a line of which head begins with '#' is a valid data line and the rest are ignored as comments. In a data line, only numerals are recognized and the other letters are all treated as separating characters. Accordingly, in stead of "#1 > 2 3", writing "#1 2 3" or "#1,2,3" comes to a description of thoroughly same content. Valid graph data must satisfy the following condition.
(1) The vertex numbers must be continuous, begin with 1 and not above 100.
(2) Don't care the order of outgoing/incoming vertex numbers.
(3) An isolated vertex which has no edge is valid.
(4) A vertex which has a self-loop is invalid.
(5) Duplicate vertices are ignored.
(6) Duplicate edges are ignored.
There are 3 kinds of output log file.
All these log files are made in the directory where Ariadne100.exe exists. It is able to re-experiment them afterward as sample graph files, as they are or after processed.
You can save the sample graph data and the experimental result into an arbitrary file at a timing when a prompt message below is displayed. This log file can be re-experimented as a sample graph file afterward just as it is.
Save the record into a log file?
Y/N
In analyzing mode, the log data and the analytical result are stored into "Ariadne.tmp" file automatically. This file is over-written when a new analyzing mode session is executed. Please rename the file and save it by necessity. This log file can be re-experimented as a sample graph file afterward just as it is.
In an automatic experiment, all sample graph
logs are stored into "Ariadne.log" file automatically. This file is over-written
when a new automatic experiment is executed. Please rename the file and save it by
necessity. Since every log of all sample graphs is stored and heaped in an automatic
experiment log file, it is probable that the file becomes rather big. You can copy data
corresponds to a graph in the log file into an independent sample
graph file and re-experiment it.
to the author. It is welcome to put the program into a curriculum for a class of undergraduate
students learning discrete mathematics and use it as a teaching material for exercises.
Students would learn empirically "real hardness of a combinatorial problem" from
Ariadne.
Timing Chart Method |
|
|
Ariadne alternatively runs two independent solutions, both of Timing Chart Method and Graph Contraction Method. Since "Graph Contraction Method" puts the experiment forward, contracting and reducing the experimental graph, the size of the objective graph rapidly becomes smaller and it finally converges into a point and ends the experiment. Graph Contraction Method being built in the experiment body algorithm remarkably improves the experimental efficiency. Regarding Graph Contraction Method, please refer to another article "A Study of Hamiltonian Circuit Problem". Only a part of the algorithm relates to Timing Chart Method shall be explained here.
In the solution of this experiment program, we use a N*N size table named "Timing Chart". It is a lattice board having horizontally a time axis and vertically a sequence of graph vertices. Where we call a horizontal ruled line as "line" and a vertical ruled line as "step", the experiment comes to an operation to select all steps and lines one by one avoiding selecting them twice, and determine N crossing points (hereafter experiment points).
The following headings are explained.
The experiment algorithm consists of the following 4 blocks.
A. Experiment body algorithm
B. Select initial point algorithm
C. Select step algorithm
D. Select point algorithm
(1) Call a select initial point algorithm and
determine initial point S.
(2) On the timing chart, generate a hasse-diagram consists of all paths that goes from S
and returns to S in exactly N steps.
(3) Call a select step algorithm and determine step t.
(4) Call a select point algorithm and select point p.
(5) Remove all the experiment points and their branches on line p and step t, except the
experiment point (p, t).
(6) Remove experiment points which dropped out by losing all of output/input branches from
the hasse-diagram. Repeat this until no dropped point occurs.
(7) When a fault occurs (a case when a line or a step is totally omitted), repeat (4) and
try another undetermined experiment point.
(8) Backtrack if fail in all of the undetermined experiment points of the step.
(9) Proceed to (3) if succeed to determine an experiment point.
(10) If succeed to determine an experiment point at every step, judge the graph as
"hamiltonian" and end.
(11) If fail in all of undetermined experiment points of the first selected step
(ordinarily step 1), judge the graph as "non-hamiltonian" and end.
There exists a plural of select initial point algorithm.*1
a. Algorithm that selects the minimum branches number point.
b. Algorithm that selects the maximum branches number point.
c. Algorithm that generates a hasse-diagram for each point of the graph and applies the
evaluation of the diagrams to the selection, and so on.
There exists a plural of select step algorithm.*1
a. Algorithm that selects a step of the minimum number of undetermined points.
b. Algorithm that selects a step of the maximum number of undetermined points.
c. Algorithm that applies branches number of experiment points, number of the occurrences
of point fault, or else to the selection, and so on.
There exists a plural of select point algorithm.*1
a. Algorithm that selects the minimum branches number point.
b. Algorithm that selects the maximum branches number point.
c. Algorithm that applies the evaluation of other status parameters to the selection, and
so on.
*1 See Regarding Complexity.
Although there is some difference in the movement between auto-experiment and manual experiment, the experiment mechanism implemented in "Ariadne" acts approximately through the following general flow.
(1) Generation of a sample graph
(2) Plain hamiltonian experiment
(3) Choice of methods
(4) Auto-selection of an initial point
(5) Analyzing mode
(6) Standard experiment
(7) Display of the experimental result
Set the parameters, then it makes a sample graph automatically. A graph data file can be read. (All data saved as log can be read as graph data file afterward.) In the automatic-experiment mode, every graph data is shuffled in this phase. (Shuffle = randomly change a labeling of a graph)
Performs a hamiltonian experiment using prearranged most simple algorithm. It breaks when the fault rate exceeds 0.5. It ends when a judgment was obtained in the plain experiment. Every time when it determines an experiment point (by one experiment count), it outputs a display-status-line in following format on your screen. See (7)Display of the experimental result.
Experiment ct=28 sc=48 pr=0.0004902906378601 fr=0.3- ex=2.8- rt=04:31:48
1. Experiment: test mode name. displays the following by the experiment configuration.
Experiment :Hamiltonian plain experiment (the first inning)
Analyzing :Analyzing mode
Hamiltonian :Hamiltonian experiment (method 1)
Searching :Hamiltonian Search (method 2)
StraitTest :Same with the Experiment above(method 3)
NonHamilton :Non-hamiltonian experiment (method 4)
Traversing :Non-hamiltonian search (method 5)
2. ct: experiment count. number of experiment points determined in the current
experiment.
3. sc: experiment score. number of valid experiment points currently determined
4. pr: progress. progress rate of the current experiment. it becomes 1.0 when a
non-hamiltonian experiment ends. it is a sum of real numbers, divided initial value 1.0 by
branches number at every divergence of the search tree. Every time when a fault occurs,
the value corresponds to the point is added. 0, at the state where no fault has occurred.
5. fr: fault rate = failed experiment points number/experiment count. when the
fault rate exceeds 1.0, +mark is put.
6. ex: experimental exponent = estimated complexity of the experiment. when the
exponent exceeds logN, +mark is put.
7. rt: estimated remaining time. estimated required time to complete the
experiment, counted backward from the current progress.
Choose a method from among 3 hamiltonian methods and 2 non-hamiltonian methods. when the experiment failed, returns to this phase, then choose another method. Although a method is a combination of said B*C*D algorithms, the release version only uses 5 sorts among them.
Labyrinth pattern appears. Generates a hasse-diagram for each point and selects an initial point by comparing and evaluating the diagrams
Giving shuffles, performs sham experiments in prearranged times(N/6 times). if a judgment is obtained in the analyzing, it ends. Evaluates the results of the sham experiments and executes the standard experiment of the next phase using the stake of the best odds. The analytical result is saved automatically in the analysis log file (Ariadne.tmp). See Regarding Complexity.
Using chosen method and the stake(the winning number) taken by the analytical result, executes the standard experiment. It breaks when a fault rate exceeds 1.0 in a hamiltonian experiment and returns to (3). It pauses when a value called "deviation" exceeds a prearranged value in a non-hamiltonian experiment (since it is almost definite that the graph is non-hamiltonian and perhaps the experiment takes so much time till it ends). If "Y" is selected, it continues the experiment. At the case selected "N", it ends. When a judgment is obtained, it displays the experimental result and ends.
Displays the experimental result in the following format.
11-10-75-25-83-35-95-39-27-8-20-73-76-34-92-7-31-63-41-65-47-57-50-79-62-29-96-24-
42-44-6-33-18-98-74-32-22-88-77-68-82-37-13-90-69-19-46-9-85-64-84-15-30-12-78-60-
14-38-99-52-91-61-55-67-43-5-54-56-21-23-40-70-94-66-58-53-3-26-86-87-28-48-49-4-
17-81-97-1-36-89-72-80-45-59-93-16-2-71-100-51-11-
This rand5150.txt is a hamiltonian graph! abtabt abtabt a
abtabMon Aug 14 19:36:07 2000
Test No.1: graph file name=rand5150.txt
Analysis: "Extremely Hard" searching, method=101, under faults
shuffled: 13th in 16 stakes, status=1, start point=11
N=100(68), M=364(234), L=164: degrees max=8, min=1, ave=4
trails=1.502390e+033, progress=0.7499999999999985, required time=00:14:05
total count=5521, experiment count=4633, fault count=3764, fault rate=0.81
complexity=L^1.69, logN=4.61, exponent=1.71, gradient=2.69, entropy=2.216026
1. hamiltonian circuit: a sequence of vertices. doesn't display in
non-hamiltonian case.
2. judgment: a notice string of judged result, the date and the time
3. Test No.: experimentation number. serial number of the sample graph since the
program was executed.
4. graph description: displays proper data such as the sample graph name,
parameters setting, etc.
5. Analysis: remark + experiment form. displays the difficulty in 6 grades bellow.
Easy, Hard, Very Hard, Extremely Hard, Ultimately Hard, Intractable
These remarks are due to the value classification of deviation.
6. method: inner code of the experiment algorithm
7. under faults/over faults: the fault rate exceeds 1.0/doesn't exceed.
8. shuffled/un-shuffled: the graph was shuffled/not shuffled
9. xxth in yy stakes: the xxth stake within yy shuffles
10. status: end code. +1:hamiltonian graph, <0:non-hamiltonian graph
11. start point: the label of the initial vertex
12. N = xx(yy): vertices number of the graph(vertices number of initial
contraction)
13. M = xx(yy): edges number of the graph(edges number of initial contraction)
14. L: complexity base= M-2N. a base number for the
calculation of complexity/exponent.*2
15. degrees max, min, ave: maximum, minimum and average number of outgoing edges of
the graph vertices.
16. trails: number of distinctive N steps trails from S to S on the hasse-diagram
17. progress: experiment progress rate. It becomes 1.0
when non-hamiltonian experiment ends.*2,*3
18. required time: required time for the experimentation (includes the plain
experiment, analyzing time, and user response time)
19. total count: sum of the experiment counts since the experimentation starts.
(includes the counts in the plain experiment and analyzing)
20. experiment count: the total number of determined
experiment points in the experiment where the judgment was obtained.*2
21. fault count: the total number of failed experiment points in the experiment
where the judgment was obtained.
22. fault rate: the fault rate = fault count/experiment
count. It breaks when the fault rate exceeds 0.5 in a plain experiment. It breaks when the
fault rate exceeds 1.0 in a hamiltonian experiment.
23. complexity: experimental complexity = log(total
count)/log(L).*1,*2
24. logN: logarithm*1 of
the graph vertex number N, a target value of the experimental complexity.*2
25. exponent: experimental exponent =(log(experiment
count)-log(progress))/log(L)*1. At the end of
experiment, exponent <= logN is a mark of the experiment.*2,*3
26. gradient: progress gradient = logN/exponent.
gradient >= 1.0 is a mark of the experimentation.*2
27. experimental entropy: experimental amount of
information = -sum(plogp)*1, where
let divergency rate (success probability) of a fault point of the search tree be p.
This value is the information amount of "definite information if the graph is a
hamiltonian or not".
*1 All logarithms used in this
program are natural logarithms with base e.
*2 See Regarding Complexity.
*3 See also (2) Plain hamiltonian experiment.
Regarding Complexity |
|
|
The following headings are explained.
We propose to change the rule of the game for solving Hamiltonian Circuit Problem realistically. The North Kanto Rule is the following relaxed condition of standard Hamiltonian Circuit Problem. Of course this relaxed rule is applicable to the whole NP-complete problem.
(1) Not polynomial time but (exponentially) logarithmic time order is admitted.
(2) Parallel machines (or plural algorithms) can be used to solve a problem.
(3) To shuffle the graph (change the labeling of the graph randomly) is admitted.
This is not a proposal to substitute it for the formal rule of professional basketball game and to play by a childish rule for elementary schoolboys. Look back the history, either UNIX or C language began with the resignation from constructing a preceding huge and super-complex system respectively. This proposal of us is not to "Take the easy way out." but our manifestation to "Solve it as far as we can.". See Regarding Complexity.
From a point of view of a practitioner who believes NP=P and is trying to give it an actual proof, (1) may look like a violence unacceptable, but "it is necessary for your program to pass the gate" and even if you did it, the credit of your program would never be damaged.
Most of all existing programs apply "plural algorithms" as a matter of fact by the ways of setting options, choosing algorithms explicitly or else. Probably you will notice that they are the "specification" after all. We forecast "the number of parallel machines necessary might stay within linear order of N".
We have called a solution of Hamilton Circuit Problem "a mathematically proved way to reach one's fortune". However our final conclusion is "To get the fortune, the chance is necessary as well.". It is natural that you have a suspicion "How is it able to prove that the problem can be definitely solved after introducing a chance." But from the empirical facts obtained by our persistent observation, there are distinctive features in each success paths and failure paths, and such a hypothesis surfaces that the number of those features is unexpectedly small (i.e., we can find out it by trials of some finite times).
Please let me hear your opinion to the proposal to change the rule of the game, NP-Complete.
In the complexity theory, complexity of a problem is measured by the steps of the algorithm to solve the problem. In this sense, complexity in Ariadne is indicated by the experiment count. We pay attention to the power of a base number L(complexity base) and call it experimental complexity. See (7)Display of the experimental result.
expcount=L^complexity
log(expcount)=complexity*log(L)
complexity=log(expcount)/log(L)
Currently we assign M-2N to the base number L. Accordingly L=O(N^2). Although graphs we operate are directed graphs, concerning undirected graph, the number L corresponds to (Euler number)*2. As we operate a table N^3 size at inside logic of the experiment, it possibly takes a calculation cost of O(N^4) by 1 experiment count. Consequently, usual meaning Complexity is
Complexity=O(N^4*(N^2)^complexity).
Our target (under the North Kanto Rule) is to suppress complexity<=logN. Namely,
expcount<=L^logN
is our target for the experiment. At the first clause of the North Kanto Rule, saying "exponentially logarithmic time order" means this.
As the indicators on experimenting, there are experimental progress rate and experimental exponent. Progress rate is a sum of a value at each fault point, where let the value at root of the search tree be 1 and divide evenly the number by the branches number at every middle node. When it is established for the graph to be non-hamiltonian, it comes progress=1. The value of experimental exponent is given by
exponent=(log(experiment count)-log(progress))/log(L).
The ratio of logN to exponent, logN/exponent is called progress gradient. If gradient>=1 holds at anytime on experimenting, this experiment will surely succeed (under North Kanto Rule). We do not yet obtain the proof of the theorem of "For given graph G, there exists a search path where the progress gradient is always greater than or equal 1", but we consider the probability that it holds is sufficiently high.
It is considered that exponent or gradient is a parameter which does not alter but very slowly, even looking from the definition. Hence in ordinary case, it is able to estimate rather early in an experiment whether the experiment is hopeful to succeed or not.
The principal factors relate to the complexity of a non-hamiltonian experiment are the following two.
(1) Labeling(shuffling) of the objective graph
(2) Select initial point algorithm and select step algorithm
The reason why a labeling of the graph effects to the complexity is that there is some "arbitrary selection" in an algorithm. It is apparently impossible to compose a completely deterministic algorithm. (To do so, it needs complete analysis of the graph and the analysis will probably take exponential time.) See (5)Analyzing mode.
Where our method differs from the thorough examination is that the complexity alters due to the applicability of the select initial point algorithm and select step algorithm. That is, those algorithm decides the shape of the search tree (=nodes number).
It can be said that a select point algorithm
principally doesn't relate to the complexity of a non-hamiltonian experiment. (Because the
complexity does not change by the selecting order of experiment points as it tests every
undetermined point.) However, finally it may effect to the complexity since it alters the
winning number in the trial and evaluation, namely analyzing phase. (In a hamiltonian
experiment, the applicability of a select point algorithm must be the factor most effects
to the performance.)
The first opponent of Ariadne's debut match was SAT01 of Stanislav Busygin and she got a knockout at the first round. When every vertex of a vertices subset S of graph G is not adjacent to each other, S is said to be an independent set of G. The problem introduced by Busygin is such an undirected graph relates to MIS(Maximal Independent Set) as below.
A graph G, when it has the only maximal independent set S, any other vertex pair of G is joined and |S|>N/2. The graph G has no hamiltonian cycle.
Ariadne couldn't solve even such a small graph as 20 vertices and |S|=11. However this graph is not the unknown for us. (Refer to Mesh-Diagram Experiment) This graph has a characteristic not to have a 2-factor. In our Semi-point Graph Method, a 2-factor of graph G turns to a 1-factor of the semi-point graph of G. A problem to seek 1-factor of a semi-point graph is equivalent to a problem to seek a perfect matching of corresponding bipartite graph. The Semi-point Graph Method can solve this problem easily. (There exists a polynomial time algorithm for perfect matching problem.)
Before we began the development of Ariadne, we had finished to design a solution algorithm using Semi-point Graph Method. Even the project code of this program was decided to be "Swallowtail Butterfly". This algorithm is the one completed finally from a method which was very hard to be understood, got started in the "Draft" but interrupted, and called "Non-Temporal Experiment" or "Retrieval Transformation on Revival Tree". The origin of this code name comes from such motion of the solution that once climbed straight (like a hairy caterpillar) to the top of the search tree, it never retreats (maybe casts off the skin) and investigates only the terminal nodes one after another (just like a butterfly turns around from flower to flower).
Nevertheless, as it was understood that even this algorithm could not avoid a thorough enumeration after all, we turned to the "Timing Chart Method". The reason why we intend to retrieve the STB is principally that Ariadne is too heavy in weight. Since Ariadne uses N^3 size table inside, 100 vertices graph is almost its limit. As STB can do without using such a big table, it may treat larger problems. Above all, it may be the strongest motive that we want to realize this algorithm at least once.
We decided to rename the solution program called "Swallowtail Butterfly" so
far to "Gordian Knot". It sounds rather stronger. As this is a ring name, it
must be the name likely strong. The name Gordian Knot was presented by Sato-san of MCI. It
was told that the tangled knot, with which the king of Phrygia sealed a tank, had received
an oracle of "Anyone who untie it shall rule Asia.". Alexander the Great drew
out his sword and cut down at one blow in place of untying it. NP-Complete Problem is
apparently the Gordian Knot. By whom and when shall it be untied?
However we could retort hajo graph upon Busygin. SAT01 is behind Ariadne by one step at hajo graph. It is the common understanding of both of Busygin and us that Ariadne and SAT01 are nearly equal on real power. Busygin had wrote a special HCP(Baba Lab Format)->SAT01 transformation program. (Thanks!) As well, the purpose we wrote a conversion program from HCP(Hamiltonian Circuit Problem) to SAT(satisfiable problem) was to make it possible to transform mutually between different problems included in NP-complete problem and realize the comprehensive benchmarking.
An institution, DIMACS(Discrete Mathematics and Theoretic Computer Science) under the influence of NSA(National Science Foundation), U.S., carried out a big campain titled "The Second DIMACS Challenge" for one year from September 1992. The purpose of the project was principally to build up a formal benchmark-site for SAT. In the committee of this project, Vasek Chvatal, Rutgers University, Bill Cook, Bell Communications Research and others had participated.
The project had finished long ago and all samples of the benchmark are already solved. However as I heard a voice that DIMACS benchmark is too easy as well, we thought that it is at any rate necessary to convert hajo graph to SAT. Ariadne can generate infinite sample graphs of various types. Even random graph experiment outputs at least one rather hard problem by one day. (There are uncountable programs which turn to impossible to solve the same problem, just by shuffling.) These sample graphs can be transformed easily into SAT files of DIMACS format.
If you have a SAT experiment program with you, please try hard Hamiltonian Circuit Problems of Ariadne by converting them to SAT. HCP->SAT conversion program is provided in Ariadne. The hardest test sample that Ariadne can generate at present is hajo graph. You can download hajo1-3.cnf.dimacs, the smallest hajo graph sample of toughness 2 or more from the URL below. The boolean formula of the problem has 625 variables and 26300 clauses.
The Hardest SAT Problem: hajo1-3.cnf.dimacs
download: hajo1-3.cnf.zip DIMACS CNF file format, 61KB
http://www.aya.or.jp/~babalabo/DownLoad/hajo1-3.cnf.zip
Whichever the result, we would be grateful to be informed the result of your test.
Ariadne can solve hajo1-3 in 42 min. (on Pentium 80MH machine!). Perhaps hajo2-5 will go over 1 year. (This numeral deviates from polynomial time but is safe under the North Kanto Rule.) Probably hajo5-11 needs 100 years, but to determine whether the solution stays in the range of North Kanto Rule or not, there is no other way but to obtain a super machine. (Ariadne calculates highly trustworthy numerical estimation, we can forecast the result to some extent by not necessarily running it to the end.) Hajo1-3 is a 25 vertices graph and hajo2-5, hajo5-11 has 42, 93 vertices respectively, small graphs.
NP-complete problem is a problem which is contained in NP and can be transformed from all NP problems in polynomial time. Cook[1971] proved that SAT(satisfiable problem of logical formula) is NP-complete. All of nearly 300 NP-complete problems known at present was confirmed by proving that the problem can be transformed from SAT. On the contrary, any concrete algorithms convert problem X to SAT are scarcely (or not at all) known.
Cook showed that all of NP problems is able to be transformed to SAT in O(P(N)^3) time by some Deterministic Machine. Where P(N) is the time complexity function of solving the original problem by Non-Deterministic Turing Machine. As P(N) is a polynomial function of N, the time complexity for the transformation comes to polynomial time. From that it follows that all of NP problem can be transformed to SAT in polynomial time. However if P!=NP, can it be indeed told? Already 30 years have passed since Cook's proof. Where is a X->SAT conversion algorithm on the earth?
Anyway, we could obtain an algorithm of O(N^3) to transform Hamiltonian Circuit Problem to SAT. The idea of the algorithm owes SAT01 of Stanislav Busygin. He collaborated with us to improve the efficiency of the algorithm. We decided to call it "HCP->SAT Conversion Cubic Time Algorithm". I'll give its outline now.
(1) Given directed graph G(V, E), N = |V|, M = |E|.
(2) Timing chart T = V*{t} = {p_it} [ i = 1 to N, t = 1 to N ].
abtaHamiltonian circuit of G is a permutation of T.
(3) Logical function U(x_1,...,x_i,...,x_k) is true iff exactly one x_i is true.
U(x_1, x_2, ..., x_k) = (x_1+x_2+....+x_k)*
abta(~x_1+~x_2)*...*(~x_k-1+~x_k) [ for all: {x_i, x_j}.i <> j,1 <= i,j <= k ]
(4) Variables of the Boolean formula = {p_it} [ i = 1 to N, t = 1 to N ].
(5) Boolean formula B = C1 * C2 * C3.
C1 =
{U(p_i1, p_i2, ... p_iN)} [ i = 1 to N ]
C2 =
C3 =
for all: i, j = 1 to N. i <> j, t = 1 to N, when t+1 = N+1 returns t+1 = 1 ]
(6) Number of variables = N^2.
abtaNumber of clauses = 2*N*(N^2-N+1-M/2).
abtaTime complexity of the algorithm = O(N^3).
Although the target of the algorithm is directed graph, quite similar in undirected graph case.
There is a probability that a (concrete) polynomial time transformation algorithm from
HCP to SAT has not been found (i.e., we first found it!). If you know something concerning
these, please let me know. I have received answers "I've never heard that..." from Vandegriend
and else several persons.
Shannon[1959] presented that an information amount can be indicated as statistical uncertainty (entropy). Vladimir Nuri expressed a very suggestive phrase "If you say that NP-complete problem is solvable in polynomial time, it is equivalent to saying that perpetual motion machine is realizable." What the second law of thermodynamics and NP-complete problem have to do with? In response to this, we made an attempt to modify Ariadne and show entropy of graph.
Definition of entropy by leaf set of tree:
Let the probability of an event X be P(X). For an event set A = {A1, A2,...,Am}, when
P(Ai)>0 and 
(P(Ai)) = 1 [ i = 1 to m ], we say this event set is a complete event system
and the entropy H is given by the equation,
H = -
Let a leaf of rooted tree T be L(i) and a set of all leaves of T be Ls = {L(i)}.
Divergent rate Pd(i) assigned to a leaf L(i) of T is a value obtained, when let the value
at root of T be 1, divide it evenly by the divergent number at every divergence of inner
nodes of T and reached to the leaf. As T is a rooted tree, this value is determined
uniquely. Whereupon obviously Pd(i) > 0 and (Pd(i)) = 1 [ i = 1 to |Ls| ], hence leaf set
Ls makes a complete event system and the entropy is given by
H(Ls) = -
In an experiment of graph G, when it is established for G to be non-hamiltonian, search
tree Ts of G is determined and the fault point set Fs makes leaf set Ls in the sense
above. Consequently let a divergent rate at each fault point F(i) be an assigned portion
of experimental progress rate for the point, Pf(i), then entropy H(Fs) of the fault point
set Fs is given by H(Fs) = -(Pf(i)log(Pf(i))).
Let entropy H(Fs) be experimental entropy, the entropy can be considered to be the information amount* of the information of "G is a non-hamiltonian graph." At the timing of initializing experiment, there exist N*N experiment points on the timing chart (almost uniformly, no particular step/line with higher priority). This state is a status, maximum entropy and minimum information amount. To get the information of "G is a non-hamiltonian graph." or "G is a hamiltonian graph.", it takes some communication cost to pull out the information. This cost is generally called Complexity.
The experimental complexity that we defined is the number of inner nodes of search tree Ts, experimental count represented in logarithm as previously mentioned in "Regarding Complexity". As generally the greater expcount or complexity means the greater size of search tree Ts, as well the size of fault point set Fs(leaves set of Ts) becomes large and the entropy augments. Is the theorem provable, "A search which gives minimum entropy has minimum complexity."? Or again, does "minimum entropy = minimum complexity" hold?
The shape of this search tree Ts changes by the algorithm applied.
Existence theorem 1: There always exists such an algorithm as expcount <= L^O(logN).
Existence theorem 2: There always exists such an algorithm as expcount <= L^O(1).
We assume that the above existence theorem 1 is provable. For the sake of NP=P, it is
necessary that the existence theorem 2 is proved. Don't you know any technic to prove the
existence or the absence of an algorithm? I would very much appreciate receiving your
information.
* base 2 logarithm expression can be obtained by entropy/log2. This value is generally called bit number (of the information).
If you have anything to notice about this program, feel free to make contact
Michiro Nasu 6.10.2000
updated M.N. 8.20.2000
last corrected m.n. 8.23.2000
|
|
1-1. Auto random graphs 1-2. Mesh graph series 1-3. Peterson graph series 1-4. Hajo graph series 1-5. Diamond graph series 1-6. Polyhedron graph series 1-7. Graph file names list 1-8. Hamiltonian world tour 1-0. Quit
- 2. Random graph
- 3. Mesh graph
- 4. Peterson graph
- 5. Hajo graph
- 5-1. original hajo graph
- 5-2. hajo+1 graph (hamiltonian)
- 5-3. super hajo graph
- 5-4. ultra hajo graph
- 6. Diamond graph
- 7. Polyhedron graph
- 8. Read File
- 9. Convert File
Ariadne100 Index