25
$\begingroup$

In connection with the Slither Link puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all possible simple cycles.

One way to do this would be to use a Markov chain whose states are sets of squares whose boundaries are simple cycles and whose transitions consist of choosing a random square to flip and keeping the flip when the modified set of squares still has a simple cycle as its boundary. One can get from any simple cycle to any other one in this way (using standard results about existence of shellings) so this eventually converges to a uniform distribution, but how quickly?

Alternatively, is there a better Markov chain, or a direct method for selecting simple cycles?

ETA: See this blog post for code to calculate the number of cycles I'm looking for, and pointers to OEIS for some of these numbers. As we know, counting is almost the same thing as random generation, and I infer from the lack of any obvious pattern in the factorizations of these numbers and the lack of a formula in the OEIS entry that there unlikely to be a known simple direct method. But that still leaves the questions of how quickly this chain converges and whether there's a better chain wide open.

$\endgroup$
  • 1
    $\begingroup$ The boundary of the sets counted by the OEIS sequence are not necessarily simple cycles, for example for 3x3, one of the 218 has all squares except the middle, and another four are given by further removing one corner. $\endgroup$ – Colin McQuillan Mar 14 '11 at 21:16
  • 1
    $\begingroup$ For 2xn grids the numbers are as given in oeis.org/A059020. For 3xn I'm pretty sure they are 6,40,213,1049,5034,23984,114069,542295,2577870,12253948,58249011,276885683,1316170990,6256394122,29739651711,141366874247,... (not in OEIS). I set up the transfer matrix to calculate it by hand but I compared it to a machine-generated matrix and the only entry they differed the hand one was correct and the machine one was wrong. (This should show up in the 3x3 case — the machine matrix would have allowed an octomino with a hole in the center.) $\endgroup$ – David Eppstein Mar 16 '11 at 7:12
  • 1
    $\begingroup$ You should send that sequence to Neil Sloane so he can put it in the OEIS. $\endgroup$ – Peter Shor Mar 16 '11 at 12:59
  • 1
    $\begingroup$ @David: Thank you. Probably, it's time for me to learn the transfer matrix method more thoroughly. $\endgroup$ – Yoshio Okamoto Mar 20 '11 at 1:48
  • 2
    $\begingroup$ @David: You just wasted two hours of my life with that link to the puzzle.. Thx! $\endgroup$ – domotorp Mar 20 '11 at 18:24
1
$\begingroup$

It seems that because you are only using the counts for number of cycles in a graph to randomly choose a cycle, that if you had a random approximation for this number, then you could still choose a cycle approximately uniformly.

Note that the number of cycles in a graph $G$, which contains edge $(u, v)$, equals the number of cycles in $G - (u, v)$ plus the number of simple paths from $u$ to $v$ in $G - (u, v)$. Thus, with a polynomial time approximation for the number of $u$-$v$ paths, the a polynomial time approximation can be achieved by incrementally building up to $G$ one edge at a time, approximating as you go.

I actually think that there's a more straightforward method for choosing a cycle. Let $G$ be the entire graph of edges around the $n \times n$ grid of squares. For each edge $(u, v)$ find the number of cycles containing that edge (which is the number of $u$-$v$ paths in $G$ - $(u, v)$). Then randomly choose an edge weighted by the number of cycles that contain it. This will be the first edge in your randomly chosen cycle. All other edges will be chosen by extending one edge at a time.

Assume that you have chosen a path which is part of your random cycle. Let the set of vertices on this path be $C$ and let $v_s$ and $v_e$ be the endvertices of the path. Also let $N$ be the set of neighbors of $v_e$ which are not in $C$ (note that there are only up to 3 in this particular graph). For each $u \in N$ count the number of $u$-$v_s$ paths in the induced graph $G[V - (C - \{v_s, v_e \} ) ]$. Then choose a neighbor, $u$, of $v_e$ weighted on the paths just counted. Add the edge $(v_e, u)$ to your chosen path, extending it by one.

In this way, a polynomial number of edges are chosen, each requiring a small number of calculations of a polynomial time approximation algorithm. Thus, a cycle can be uniformly chosen.

I currently have a stackexchange question requesting references for fast path count approximation algorithms. I've read in a few places that these algorithms exist but haven't yet found them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.