For a random graph $G$ of minimum degree 3, can we find a Hamilton cycle in linear time (with high probability for every edge density)?
If this is an open problem, I will also accept an empirically tested (on large graphs) conjectured linear time algorithm. (Quasilinear time is also interesting.) Here is what I know.
Related problems
We expect that for appropriate parameters (like edge density) the following are hard:
- Random $k$-SAT.
- For a random graph, finding a cycle whose length is within $εn$ of the maximum.
- Travelling salesman on a random connected graph with unit edge costs and required distance within $εn$ of the minimum.
- Hamilton cycle for random graphs whose local structure consists of appropriate gadgets so that we likely get local solutions (partitions into non-cyclic paths with all endpoints on the region boundary), but find it hard to combine them globally.
By constrast, the Hamilton cycle problem is easy for random graphs: If edges are placed at random, we either have lots of edges, or we likely have a local obstruction, like a vertex of degree 0 or 1, or three degree 2 vertices joining in a vertex. The question (especially the extension below) is essentially whether random Hamilton cycle is still w.h.p. easy (even linear time) if we disallow local obstructions. One reason to expect $n^{O(1)}$ time is that (vertex) disjoint cycle cover (of vertices) is in P for all graphs (here), while randomness works against short cycles.
A likely algorithm
Here is an outline of a likely linear time algorithm for the question, or at least enough to convince me that there is one. It should work in linear time even on pointer machines, and should be adaptable for quasilinear size polylog depth circuits.
After randomly (or otherwise) choosing edges (at most two incident on each vertex), we get a structure resembling a Hamilton cycle, but with local defects (plus possible extra loops). A defect can be a path endpoint or an unused vertex, but the latter can be considered as two path endpoints. With few exceptions, the local structure of $G$ is a tree (with minimum degree 3), which allows us to move a path endpoint defect, and with at least four choices for every distance 2 move. Two endpoints at distance 1 can be joined, and for this, we search for paths leading to joins. By doing this on multiple defects in parallel, we should only need to consider an average of $O(ε^{-1/2})$ different paths per defect at defect density $ε$, so we can eliminate them all in linear time.
We then decompose the structure into cycles, which we will maintain in a data structure. A random 2-regular graph has $Θ(\log n)$ cycles and a $Θ(n^{-1/2})$ chance of being a length $n$ cycle. We repeatedly break small cycles, and randomly recombine the defects at a distant location, and thus increase the minimum cycle size to $Ω(n/\log n)$ after $\log^{O(1)} n$ moves. For the remainder, we rely on the above $Ω(n^{-1/2})$ chance, noting that we can search $O(n^{1-ε})$ recombination possibilities of polylog depth and that a random path would likely touch all large cycles.
With a polynomially small probabilty (for $O(1)$ average degree), we return 'no' due to a local obstruction to Hamiltonicity. The probability of superlinear time (or just bad enough linear time) should be superpolynomially small. There is also a separate question of expected time given existence of rare hard graphs (but with proper logic, linear expected time should be achievable).
Proving its correctness seems hard. A random graph with minimum degree 3 is (with high probability) an expander, but as evidenced by bipartite graphs with unequal parts, we need something more (plus lack of local obstructions) to guarantee Hamiltonicity, but I cannot quite formalize what it is.
Extension
I am also interested about random $G$ with:
- Minimum degree ≥2 (required for Hamiltonicity).
- No degree 2 vertices at distance 1 or 2 to each other (otherwise merge them and reduce the problem).
- No odd cycle of degree 3 vertices with a degree 2 vertex on the side of each (required for Hamiltonicity).
The above properties require $≥\frac{4}{3} n$ edges (with the interesting case of $\frac{4}{3} n$ edges discussed here) and apparently w.h.p. disallow local obstructions to Hamiltonicity for random graphs. The above propagation of defects still works without dead ends (for a single defect when the local structure is a tree), which should give a linear time (w.h.p.) algorithm for $\frac{4}{3} n + Ω(n)$ number of edges — unless the structure somehow conspires to make defect propagation highly nonrandom. Whether that happens at $\frac{4}{3} n + εn$ edges deserves testing. We get there long (as in typically $Θ(ε^{-1})$) chains of degree 3 vertices with degree 2 vertices on the side (and thus without branching of propagation), and whether we get a choice at a chain branch point is situational.
Literature and Concluding Notes
From literature search, including Hamilton Cycles in Random Graphs: a bibliography by Alan Frieze:
- Without a minimum degree requirement, the Hamilton cycle problem is solvable in $O(n)$ time w.h.p. and without errors (arXiv:2111.14759). However, the Hamiltonicity threshold there is at $(1+o(1))\log n$ average degree. (For large graphs, for each vertex, the edges are given in random order.)
- For minimum degree 3, and for large enough ($O(1)$) average degree, there is an $n^{1+o(1)}$ algorithm (arXiv:1210.5999).
- For minimum degree 3, and for average degree either ≥5.33 or exactly 3 (i.e. 3-regular), a Hamilton cycle exists with high probability, and at least for 3-regular graphs can be found in polynomial time.
- For random 3-regular graphs, a perfect matching (or missing one vertex for odd $n$), can be found w.h.p. in linear time (arXiv:1808.00825).
Thus the question appears to be open. However, asymptotics for graph problems is often hard. I do not know whether the difficulty is merely confirming that certain random-like variables are in fact effectively random, with a possibly linear time algorithm already known in practice.
