<p>For a random graph <span class="math-container">$G$</span> of minimum degree 3, can we find a Hamilton cycle in linear time (with high probability for every edge density)?</p>
<p>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.</p>
<p><b>Related problems</b></p>
<p>We expect that for appropriate parameters (like edge density) the following are hard:</p>
<ul>
<li>Random <span class="math-container">$k$</span>-SAT.</li>
<li>For a random graph, finding a cycle whose length is within <span class="math-container">$εn$</span> of the maximum.</li>
<li>Travelling salesman on a random connected graph with unit edge costs and required distance within <span class="math-container">$εn$</span> of the minimum.</li>
<li>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.</li>
</ul>
<p>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 <span class="math-container">$n^{O(1)}$</span> time is that (vertex) disjoint cycle cover (of vertices) is in P for all graphs (<a href="https://cstheory.stackexchange.com/questions/8563/partition-a-graph-into-node-disjoint-cycles/8570#8570">here</a>), while randomness works against short cycles.</p>
<p><b>A likely algorithm</b></p>
<p>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.</p>
<p>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 <span class="math-container">$G$</span> 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 <span class="math-container">$O(ε^{-1/2})$</span> different paths per defect at defect density <span class="math-container">$ε$</span>, so we can eliminate them all in linear time.</p>
<p>We then decompose the structure into cycles, which we will maintain in a data structure.  A random 2-regular graph has <span class="math-container">$Θ(\log n)$</span> cycles and a <span class="math-container">$Θ(n^{-1/2})$</span> chance of being a length <span class="math-container">$n$</span> cycle.  We repeatedly break small cycles, and randomly recombine the defects at a distant location, and thus increase the minimum cycle size to <span class="math-container">$Ω(n/\log n)$</span> after <span class="math-container">$\log^{O(1)} n$</span> moves.  For the remainder, we rely on the above <span class="math-container">$Ω(n^{-1/2})$</span> chance, noting that we can search <span class="math-container">$O(n^{1-ε})$</span> recombination possibilities of polylog depth and that a random path would likely touch all large cycles.</p>
<p>With a polynomially small probabilty (for <span class="math-container">$O(1)$</span> 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).</p>
<p>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.</p>
<p><b>Extension</b></p>
<p>I am also interested about random <span class="math-container">$G$</span> with:</p>
<ul>
<li>Minimum degree ≥2 (required for Hamiltonicity).</li>
<li>No degree 2 vertices at distance 1 or 2 to each other (otherwise merge them and reduce the problem).</li>
<li>No odd cycle of degree 3 vertices with a degree 2 vertex on the side of each (required for Hamiltonicity).</li>
</ul>
<p>The above properties require <span class="math-container">$≥\frac{4}{3} n$</span> edges (with the interesting case of <span class="math-container">$\frac{4}{3} n$</span> edges discussed <a href="https://mathoverflow.net/questions/427292/hamilton-cycles-in-random-graphs-with-just-enough-connectivity">here</a>) 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 <span class="math-container">$\frac{4}{3} n + Ω(n)$</span> number of edges — unless the structure somehow conspires to make defect propagation highly nonrandom.  Whether that happens at <span class="math-container">$\frac{4}{3} n + εn$</span> edges deserves testing.  We get there long (as in typically <span class="math-container">$Θ(ε^{-1})$</span>) 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.</p>
<p><b>Literature and Concluding Notes</b></p>
<p>From literature search, including <a href="https://arxiv.org/abs/1901.07139" rel="nofollow noreferrer">Hamilton Cycles in Random Graphs: a bibliography</a> by Alan Frieze:</p>
<ul>
<li>Without a minimum degree requirement, the Hamilton cycle problem is solvable in <span class="math-container">$O(n)$</span> time w.h.p. and without errors (<a href="https://arxiv.org/abs/2111.14759" rel="nofollow noreferrer">arXiv:2111.14759</a>).  However, the Hamiltonicity threshold there is at <span class="math-container">$(1+o(1))\log n$</span> average degree.  (For large graphs, for each vertex, the edges are given in random order.)</li>
<li>For minimum degree 3, and for large enough (<span class="math-container">$O(1)$</span>) average degree, there is an <span class="math-container">$n^{1+o(1)}$</span> algorithm (<a href="https://arxiv.org/abs/1210.5999" rel="nofollow noreferrer">arXiv:1210.5999</a>).</li>
<li>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.</li>
<li>For random 3-regular graphs, a perfect matching (or missing one vertex for odd <span class="math-container">$n$</span>), can be found w.h.p. in linear time (<a href="https://arxiv.org/abs/1808.00825" rel="nofollow noreferrer">arXiv:1808.00825</a>).</li>
</ul>
<p>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.</p>

CC BY-SA 4.0
2022-08-01T02:15:48.000Z
What is your model of a random graph with given minimum degree? The one in the Frieze paper appears to be to choose enough random edges (Theta(n log n)) to be above the threshold for minimum degree, but that is different from uniformly random graphs of the given minimum degree (which is much denser, more or less the same as G(n,1/2)) and different from random 3-regular graphs.
David Eppstein
CC BY-SA 4.0
2022-08-01T02:24:22.653Z
@DavidEppstein For minimum degree $k$, $n$ vertices and $m$ edges, we place the edges at random, and then condition on each vertex having at least degree $k$.
Dmytro Taranovsky
<cc.complexity-theory><ds.algorithms><graph-theory><graph-algorithms><hamiltonian-paths>
Finding Hamilton cycles in random graphs
Dmytro Taranovsky
# Finding Hamilton cycles in random graphs

(Asked by: username_0 on 2022-07-28)

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](https://cstheory.stackexchange.com/questions/8563/partition-a-graph-into-node-disjoint-cycles/8570#8570)), 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](https://mathoverflow.net/questions/427292/hamilton-cycles-in-random-graphs-with-just-enough-connectivity)) 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](https://arxiv.org/abs/1901.07139) 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](https://arxiv.org/abs/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](https://arxiv.org/abs/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](https://arxiv.org/abs/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.

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, graph-algorithms, hamiltonian-paths

> **Comments:**
> **username_1**: What is your model of a random graph with given minimum degree? The one in the Frieze paper appears to be to choose enough random edges (Theta(n log n)) to be above the threshold for minimum degree, but that is different from uniformly random graphs of the given minimum degree (which is much denser, more or less the same as G(n,1/2)) and different from random 3-regular graphs.  
> **username_0**: @DavidEppstein For minimum degree $k$, $n$ vertices and $m$ edges, we place the edges at random, and then condition on each vertex having at least degree $k$.  

---

## 0 answers

