hmmmmm's blog

Hamiltonian of random graphs
By hmmmmm, 4 weeks ago, In English

Suppose we have $$$n$$$ vertices and we add edge $$$(i, j)$$$ with probability $$$p$$$. Is there a way to check if it is hamiltonian path/cycle or to find the longest non-self-intersecting path/cycle in polynomial time?

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

How to solve $$$p = 1$$$ xD

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Output the identity permutation.

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

NP Harder?

→ Reply
  • »
    »
    4 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +23 Vote: I do not like it

    Yes, this is NP-hard as phrased. The random graph model used here, $$$G_{n,p}$$$, is supported on all $$$n$$$-vertex graphs (for $$$p \neq 0,1$$$). So, solving this question as phrased amounts to solving longest path/Hamiltonian cycle.

    However, there is a related question which can have nontrivial answers. For specific values of $$$p$$$ like $$$p = 0.5$$$, or specific growth functions such as $$$p = \frac{1}{\sqrt{n}}$$$, the distribution of graphs coming from $$$G_{n,p}$$$ is weighted towards certain graphs. So, we could ask:

    "Is there an algorithm which correctly answers the Hamiltonian path decision problem at least 99% of the time, given that the input is drawn from $$$G_{n,p}$$$?"

    For some values of $$$p$$$, the algorithm can even be trivial! For instance, when $$$p < \frac{\log(n)}{n}$$$, then (with high probability) the graph will not even be connected, so we can always output "no Hamiltonian cycle detected" and be right 99% of the time. Similarly, when $$$p > \frac{c \log (n)}{n}$$$ for a specific constant $$$c$$$, then there is a Hamiltonian path with high probability, and we can always answer yes.

    All of the above claims are only true asymptotically. So, to make an algorithm, you would have to say "for $$$n \le n_0$$$, just use the exponential algorithm. Then, for $$$n > n_0$$$, use the algorithm which succeeds with high probability."

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What about finding longest non-self-intersecting path/cycle? Also can you describe this trivial algorithm?

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +34 Vote: I do not like it

        The trivial algorithm I mentioned only works for the "decision problem" version. In this version, you only have to say "yes, there is a Hamiltonian path" or "no, there is not a Hamiltonian path"; that is, you do not need to list the path itself. I call the algorithm trivial, because it is literally either cout << "YES\n" when $$$p$$$ is "large", and cout << "NO\n" when $$$p$$$ is "small".

        Your other question, the constructive version where you have to actually spell out a longest path, is more interesting, but I don't know a good way to do it :(

        The one thing I can say is that these sorts of problems are very sensitive to the growth rate of $$$p$$$, and sometimes there are different regimes in which different techniques/restrictions apply. Crossing the "threshold" between $$$p$$$ regimes changes the flavor of the problem a lot. For instance, here, if $$$p = O\left(\frac{\log n}{n^2}\right)$$$, then there will be $$$O(\log n)$$$ edges, and we can do any brute force which is exponential in the number of edges. This is essentially fast because $$$G_{n,p}$$$ is so sparse.

        On the other end of the spectrum, say $$$p = 0.5$$$, in which case $$$G_{n,p}$$$ is rather dense. Now, there are so many edges, that we can do this: start with vertex $$$v_0$$$. Then, let $$$v_1$$$ be any vertex with an edge $$$v_0v_1 \in E(G)$$$. Such a vertex exists with probabilty $$$1 - 2^{-(n-1)}$$$. Then, let $$$v_2$$$ be any vertex not yet chosen with an edge $$$v_1v_2 \in E(G)$$$. Such a vertex exists with probabilty $$$1 - 2^{-(n-2)}$$$. Proceed this way until you have a path of length $$$n - 10$$$ (this succeeds with probability 99.9%). Among the remaining 10 vertices, just brute force all Hamiltonian paths (I didn't do the exact calculation, but there should be many, with high probability). Then, for each length-10 path, there are "4 chances" to link it with the big path (each path has 2 ends, and they may be connected either way). So, with probability $$$15/16$$$, any given path works. The probability that they all fail should be small (I didn't calculate this either; dependence is a factor). But anyway, this should succeed overall like >95% of the time.

        The weird case in these problems is always the values near the threshold. So, if $$$p = \Theta\left(\frac{\log n}{n}\right)$$$, I don't know what to expect. It may be the case that there are "very few, but more than 0" Hamiltonian paths, in which case, my instinct is that finding one in polynomial time would be difficult.

        → Reply
»
4 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

I'm no expert, but this and this will probably work well in practice

→ Reply
»
4 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

Some known results on this problem: As bpdolson mentioned, the critical window of $$$p$$$ on whether $$$G_{n, p}$$$ contains a Hamiltonian cycle is well understood: When $$$p = \frac{\log n + \log \log n + c}{n}$$$ the probability will converge to $$$e^{-e^{-c}}$$$ as $$$n\to \infty$$$. The proof can be found in the famous textbook Random Graphs by Béla Bollobás.

A recent algorithmic result (Rajko Nenadov, Angelika Steger, Pascal Su, An $$$O(n)$$$ time algorithm for finding Hamilton cycles with high probability, ITCS 2021) claims that, there exists a constant $$$C$$$ such that, for $$$p\geq C \log n / n$$$, a randomized algorithm can find a Hamiltonian cycle, even in linear time (of course, since the number of edges is already superlinear, the algorithm need some other ways to read the input).

→ Reply