Finding long cycles in graphs

We analyze the problem of discovering long cycles inside a graph. We propose and test two algorithms for this task. The first one is based on recent advances in statistical mechanics and relies on a message passing procedure. The second follows a more standard Monte Carlo Markov chain strategy. Special attention is devoted to Hamiltonian cycles of (nonregular) random graphs of minimal connectivity equal to 3.

Figure 1

Average number of steps needed for the decimation procedure to exit for graphs of different connectivity distributions (+ for $q_{3,4}^{0.5}$, × for $q_{3,5}^{0.5}$, and * for $q_{4,5}^{0.5}$) and sizes. The best fit to all data for all connectivity distributions is linear and has a slope of 0.23.

Figure 2

Integrated distribution of the number of decimation procedures needed to find a Hamiltonian cycle for graphs with connectivity distribution $q_{3,4}^{0.5}$ of various sizes ($N$ increases from left to right). (a) With and (b) without the use of the patching procedure.

Figure 3

Integrated distribution of the number of decimation procedures needed to find a Hamiltonian cycle for graphs with connectivity distribution $q_{3,4}^{0.5}$ (dotted lines), $q_{3,5}^{0.5}$ (dashed lines), and $q_{4,5}^{0.5}$ (full lines) of sizes $N=1600$. (a) With and (b) without the use of the patching procedure.

Figure 4

Possible states $j$ of the central edge with all possible corresponding nonzero transition probabilities $w_{j\to i}$. The bold lines stand for an edge, path, or cycle which is present, the thin lines mean it is absent. Two thin parallel lines separating present edges or paths signify that those edges or paths are disconnected.

Figure 5

Median of the number of moves performed before the discovery of a Hamiltonian circuit for various connectivity distributions [$q_{3,4}^{0.5}$: dotted line (+); $q_{3,5}^{0.5}$: dashed line (×); $q_{4,5}^{0.5}$ full line (◻)] in function of the size of the graphs.

Figure 6

Local rewiring in order to unite the cycles of a cycle cover (a) into a Hamiltonian cycle (b).

Figure 7

Distribution of the solution time, i.e., the time it takes to find a Hamiltonian cycle, in stochastic MC time for $N$-fold MC (long-dashed line) and MC sweeps for rejection MC (short-dashed line), of the number of moves performed (full line for $N$-fold MC, dotted line for rejection MC) and of the total number of proposed moves in rejection MC (dashed-dotted line) for graphs of size $N=800$ with degree distribution $q_{3,4}^{0.5}$.