Return to Question

EDIT: Preliminary results 1

In case there are people who are interested. Finally found some time to do some coding. Implemented branching cutting via symmetry.

PathLength-UniquePaths-NonUniquePaths:
4-1-1
5-2-3
6-4-9
7-9-26
8-22-76
9-59-218
10-160-628
11-445-1764
12-1248-4992
13-3443-13772
14-9570-38280
15-25842-103388
16-70349-281484
17-186073-744744
18-496014-1985656
19-1282138-5134244

The third column can be viewed as a simple backtracking algorithm but with first 4 vertices fixed. (Therefore symbolizing full path search)
This result seems to show that I should expect the simple symmetry of paths method to be about 4 times improvement over backtracking (consistently 4 times smaller). Simply put, it is not much of an improvement.
The unoptimized run time for path length 19 is about 400 seconds, which seems to multiply by about 2.5 per increment, where the number of unique paths also multiply by around that amount. This factor will slowly decrease as the path length increase.
  Around fixing of 30 or so vertices, it becomes instantaneous to check the remaining paths.
  By some naive estimate it seems that I can now try to brute force this in a few months...

EDIT: Preliminary results 2

I had written better pruning codes and I realized that it takes only at most a couple of weeks to finish the running. However, based on extrapolation of the initial few branches I had completed, I will need some whooping 5+ TB of hard disk space just to store the results. Comparing with just measly 24 Hamiltonian cycles for $n=5$, it seems pretty clear that even if I can find all cycles for $n=9$ there is no way I can store all of them. Sad =(

EDIT: Preliminary results 1

In case there are people who are interested. Finally found some time to do some coding. Implemented branching cutting via symmetry.

PathLength-UniquePaths-NonUniquePaths:
4-1-1
5-2-3
6-4-9
7-9-26
8-22-76
9-59-218
10-160-628
11-445-1764
12-1248-4992
13-3443-13772
14-9570-38280
15-25842-103388
16-70349-281484
17-186073-744744
18-496014-1985656
19-1282138-5134244

The third column can be viewed as a simple backtracking algorithm but with first 4 vertices fixed. (Therefore symbolizing full path search)
This result seems to show that I should expect the simple symmetry of paths method to be about 4 times improvement over backtracking (consistently 4 times smaller). Simply put, it is not much of an improvement.
The unoptimized run time for path length 19 is about 400 seconds, which seems to multiply by about 2.5 per increment, where the number of unique paths also multiply by around that amount. This factor will slowly decrease as the path length increase.
Around fixing of 30 or so vertices, it becomes instantaneous to check the remaining paths.
By some naive estimate it seems that I can now try to brute force this in a few months...

Hi everyone!

This is my first post, apologies if I made any mistakes anywhere.

Here goes the question: Consider all length 7 binary sequences. Let $X$ be the set of sequences with hamming weight 3 and let $Y$ be the set of sequences with hamming weight 4. For each vertex in $X$, connect an edge to each element in $Y$ if they differ by only 1 bit. For example, 4 edges will be connected from $0000111$ to $1000111, 0100111, 0010111$ and $0001111$.

This will result in a Bipartite Vertex Transitive graph. To be precise, the resulting graph will be 4 regular.

Now I am aware that a straight forward bruteforce of the 70 vertices will take forever and the generic dynamic programming approach of TSP is still quite unreachable due to the complexity being in the range of $O(2^{70})$.

The closest reference I come across is Finding and Enumerating Hamilton Cycles in 4-Regular Graphs, where the complexity is $O(1.783^{70})$, but still nowhere close to being solvable. I am now wondering if the additional conditions of the graph being vertex-transitive and bipartite might help be bring down the complexity. Also, there is quite a bit of "special knowledge" about the graph that we can deduce. For example, there cannot be a cycle of length 4.

Please note that this is related to Middle Layers Conjecture. I am interested to know all the Hamiltonian cycles for $k=4$ and $k=5$ (9 and 11 bit binary sequences).

I played around with the idea of using permutations to classify several paths into 1 so that only one representative needs to be checked: Let starting vertex be $0000111$ and suppose I found all Hamiltonian cycles of the form: $R-0001111-0000111-0010111-S$. It appears to me that I can extend this result by applying, say a permutation of bit 1 and 4 to all elements in the cycle to get a new class: $R-1000111-0000111-0010111-S$. Since this is a bijective function between the 2 classes, I would have effective found all cycles in the new class too. I can use this technique to reduce 6 types of cycles of the forms:

$-0001111-0000111-0010111-$

$-0001111-0000111-0100111-$

$-0001111-0000111-1000111-$

$-0010111-0000111-0100111-$

$-0010111-0000111-1000111-$

$-0100111-0000111-1000111-$

into just one case. However, I cannot find a way to generalize this approach too far down to compress more paths. I am interested to know how everyone thinks of this question. Does it seem to be solvable in practical time?

Finally, my pleasure to meet all of you!

Hi everyone!

This is my first post, apologies if I made any mistakes anywhere.

Here goes the question: Consider all length 7 binary sequences. Let $X$ be the set of sequences with hamming weight 3 and let $Y$ be the set of sequences with hamming weight 4. For each vertex in $X$, connect an edge to each element in $Y$ if they differ by only 1 bit. For example, 4 edges will be connected from $0000111$ to $1000111, 0100111, 0010111$ and $0001111$.

This will result in a Bipartite Vertex Transitive graph. To be precise, the resulting graph will be 4 regular.

How can I enumerate all Hamiltonian Cycles in this graph?

Now I am aware that a straight forward bruteforce of the 70 vertices will take forever and the generic dynamic programming approach of TSP is still quite unreachable due to the complexity being in the range of $O(2^{70})$.

The closest reference I come across is Finding and Enumerating Hamilton Cycles in 4-Regular Graphs, where the complexity is $O(1.783^{70})$, but still nowhere close to being solvable. I am now wondering if the additional conditions of the graph being vertex-transitive and bipartite might help be bring down the complexity. Also, there is quite a bit of "special knowledge" about the graph that we can deduce. For example, there cannot be a cycle of length 4.

Please note that this is related to Middle Layers Conjecture. I am interested to know all the Hamiltonian cycles for $k=4$ and $k=5$ (9 and 11 bit binary sequences).

I played around with the idea of using permutations to classify several paths into 1 so that only one representative needs to be checked: Let starting vertex be $0000111$ and suppose I found all Hamiltonian cycles of the form: $R-0001111-0000111-0010111-S$. It appears to me that I can extend this result by applying, say a permutation of bit 1 and 4 to all elements in the cycle to get a new class: $R-1000111-0000111-0010111-S$. Since this is a bijective function between the 2 classes, I would have effectively found all cycles in the new class too. I can use this technique to reduce 6 types of cycles of the forms:

$-0001111-0000111-0010111-$

$-0001111-0000111-0100111-$

$-0001111-0000111-1000111-$

$-0010111-0000111-0100111-$

$-0010111-0000111-1000111-$

$-0100111-0000111-1000111-$

into just one case. However, I cannot find a way to generalize this approach too far down to compress more paths. I am interested to know how everyone thinks of this question. Does it seem to be solvable in practical time?

Finally, my pleasure to meet all of you!