Minimum Weight Cycle Cover Algorithm

[Jelmer Firet]

I have found an algorithm that might be helpful in finding minimal superpermutations.

Given a weighted directed graph (V,E) the algorithm finds a minimal weight cycle cover of that graph (vertex-disjoint cycle cover).

The algorithm first takes each vertex of the graph and splits it in two; one vertex for all outgoing edges and one for all incoming edges.

We get an bipartite graph. On this bipartite graph we apply the Hungarian Algorithm (Wikipedia, My explanation) to find a minimum weight perfect matching.

Then finally it glues the vertices back together, then the matching will become a cycle cover.

There is still a problem we have to solve; If we apply the algorithm on the complete permutation graph we get a trivial cycle cover: all 1-cycles.

We must figure out if we can adapt the input graph such that the output is a Hamiltonian cycle, while preserving minimality.

I have two possible approaches, but haven't tested them

1. Run the algorithm multiple times, each time giving the edges of the found cycle cover a little extra weight. This might not converge to a Hamiltionian cycle.

2. Using the cycle cover found by the algorithm, set up a "chair dance" for each cycle. For each cycle of n vertices we add (n-1) chair vertices. These new vertices get a bidirectional edge of weight 0 to all vertices of the cycle. We remove all edges that belonged to the cycle cover. This forces at least one outgoing edge for each cycle, as well as at least one incoming edge for each cycle. This way we find a cycle cover over the 1-cycles but this method might not preserve minimality.

[Cole Fritsch]

I believe that this idea may be a little too hopeful. As far as I can tell, this algorithm is not dependent upon any of the rules specific to superpermutations. This would suggest that if you could get rid of these trivial cycle covers in polynomial time, you would be solving the TSP problem as a whole in polynomial time. Correct me if I am wrong about this. It is an interesting idea though.

I think the best way to find an algorithm for SPs is to use the fact that the graph is a Cayley graph on the symmetric group, with some other properties that may be special to SPs. It is amazing that we have not yet found a good algorithm for such a restrictive property of a graph. Keep thinking!

-Cole Fritsch

[Wenjie Fang | fwjmath | 方弦]

In fact I think that a closer model will be the Chinese Postman Problem (https://en.wikipedia.org/wiki/Route_inspection_problem), in which we need to fine a shortest circuit (**not exactly a path**) that passes through all nodes at least once. The unweighted directed case, which is what we are dealing with here, is in P. There is an algorithm in O(|V|^2 |E|) time. However, one should note that it finds a circuit. By introducing a new node that branches only to the identity (starting point) and another element (ending point), we can obtain an algorithm in O(|V|^3 |E|) time, with V = S_n and |E| = [n] * S_n.

Maybe I am wrong though, if I misunderstood something in the supermutations...

All the best,

Wenjie Fang

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/a3b74acb-bf74-40c3-8c87-dc52bb09a42d%40googlegroups.com.

[Cole Fritsch]

I am not sure what you mean by this. The Chinese Postman Problem seems to deal with reaching every edge exactly once, rather than every vertex like the Travelling Salesman Problem. The graph we are considering is for each permutation to be a vertex and each transition between two vertices to be an edge. A superpermutation of n is defined as a string that contains at least one substring for each of the n! permutations of n. This suggests that we want a Hamiltonian cycle for our graph, not an Eulerian circuit.

We can perform a complicated procedure to swap vertices and edges for one-another, but then we will get multiple edges that represent the same permutation.

-Cole Fritsch

[Wenjie Fang | fwjmath | 方弦]

Indeed, thank you for pointing that out. Then the Cayley graph structure must be used, either by constructing paths in cosets and glue them together, or by breaking the symmetry in the branch-and-bound algorithm. The latter is already done in the current algorithm though.

All the best,

Wenjie Fang

--

You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/347929c7-3ad5-468d-a34b-5d3ec7f67cd5%40googlegroups.com.