5
$\begingroup$

Suppose we randomly choose a graph with $n$ vertices in the following manner: each edge is included with probability $\frac12$. Thus, each graph has the same probability of being chosen, and there are $2^{\frac{n(n-1)}{2}}$ possible graphs. Denote $H_n$ the event that such a graph contains a Hamiltonian path. Prove that $$\lim_{n \to \infty} P(H_n) = 1,$$ that is, as we consider larger and larger graphs, the proportion of graphs that contain a Hamiltonian path approaches $1$.

As a bonus, find an efficient algorithm for finding a Hamiltonian path in a graph. The algorithm must also be precise, that is, it must find a Hamiltonian path most of the time. More concretely, we are looking for an algorithm with the following two properties:

  • Its average time complexity is polynomial with respect to the number of vertices. (But you should aim for as good as possible.)
  • Denote $S_n$ the event that the algorithm succeeds if its input is a random graph with $n$ vertices. Then, $$\lim_{n \to \infty} P(S_n) = 1.$$

So, what have I tried so far? There is a relatively easy way to obtain the lower bound of $0.25$ that holds for all $n$. Denote $X_n[a]$ the event that there exists a Hamiltonian path starting at $a$, in a random graph with $n$ vertices. Clearly, the probability of such an event occuring is the same for all vertices, and we will denote this probability $x$. We can bound $x = P(X_n[a])$ from below as follows:

  • If there is at least one edge to some vertex $b$, we can consider Hamiltonian paths that start with vertices $a, b$. The probability that such a Hamiltonian path exists is $P(X_{n-1}[b]) = x_{n-1}$.
  • If there is no edge from $a$, there is no Hamiltonian path starting at $a$. The probability of this occuring is $\frac{1}{2^{n-1}}$.

Thus we obtain the following inequality: $$x_n \geq (1 - \frac {1}{2^{n-1}}) \cdot x_{n-1}.$$

From this it is easy to prove that $x_n \geq \frac14$ for all $n$. To obtain a better lower bound, we can consider additional cases based on how many edges there are from $a$:

  • If there are $0$ adjacent vertices, there is no hope.
  • If there is one adjacent vertex, we can reduce to $x_{n-1}$.
  • If there are at least $2$ adjacent vertices, denote them $b$ and $c$. The path can go through either $b$ or $c$. Thus, by the inclusion-exclusion principle, the probability that at least one of the paths exists is $$P(X_{n-1}[b]) + P(X_{n-1}[c]) - P(X_{n-1}[b] \land X_{n-1}[c]).$$

Thus, if we were to find a good enough upper bound for $P(X_{n-1}[b] \land X_{n-1}[c])$, the problem would be solved. However, such an upper bound eludes me, all I can come up with are lower bounds (which are not helpful).

Alternative forms of the above expression that may help: $$P(X_{n-1}[b])\ +\ P(X_{n-1}[c] \mid \neg X_{n-1}[b])$$

In this form, we are trying to find a lower bound for the second term, which corresponds to the probability that there exists a Hamiltonian path starting at $c$, given that we know that there is no Hamiltonian path from $b$.

Also, it may be better to consider the case with more vertices adjacent to $a$, such as three. Though with more vertices comes bigger trouble when applying the inclusion-exclusion principle.

$\endgroup$
  • 1
    $\begingroup$ So are you just posting your assignment verbatim? $\endgroup$ – quasi Aug 10 '18 at 17:09
  • 1
    $\begingroup$ This is actually not an assignment, but a problem I came up with (though it seems pretty standard). However I see that here it is required of you to show that you have tried solving the problem before posting, so I will do just that in a minute. $\endgroup$ – buj Aug 10 '18 at 17:13
  • $\begingroup$ The Hamiltonian path problem is NP-complete, so this sounds like a non-starter to me. $\endgroup$ – saulspatz Aug 10 '18 at 18:27
  • $\begingroup$ Sure, but in that problem, you are not allowed to make any mistakes. In this problem, you are allowed to make mistakes, provided that as $n \to \infty$ your mistakes go to $0$. The idea is that: "There are too many edges---there must be a Hamiltonian path!" $\endgroup$ – buj Aug 10 '18 at 18:30
  • $\begingroup$ @buj: Thanks for making the effort to show your ideas (+1), and welcome to MSE! $\endgroup$ – quasi Aug 10 '18 at 18:33
3
$\begingroup$

For context: a result of Pósa says that a random graph with $C n \log n$ edges already contains a Hamiltonian path with probability tending to $1$, and here we have a uniformly random graph (with $\frac{n^2}{4}$ edges on average). So we can be fairly wasteful.

As far as an algorithm goes, we can take the algorithm used to prove Dirac's theorem. The hypotheses of that theorem don't hold here, but the algorithm will still work with high probability. The strategy is this:

  1. Pick a path greedily: start at a vertex $v_1$, pick a vertex $v_2$ it is adjacent to, then pick a vertex $v_3$ adjacent to $v_2$, and so on. Repeat until you get stuck.
  2. Turn the path into a cycle: if it has endpoints $v_1$ and $v_\ell$, find adjacent vertices $v_i$ and $v_{i+1}$ on the path such that $v_{i+1}$ is adjacent to $v_1$ and $v_i$ is adjacent to $v_\ell$. Then the cycle is $v_1, \dots, v_i, v_\ell, \dots, v_{i+1}, v_1$.
  3. Turn the cycle into a longer path: if $v_{\ell+1}$ is a vertex not on the cycle, find a vertex $v$ on the cycle adjacent to $v_{\ell+1}$, and take the path starting next to $v$, going around the cycle, and then going to $v_{\ell+1}$.
  4. Repeat steps 2 and 3 until the path contains all the vertices.

All of these steps are quite likely to work individually. The problem is that to analyze how likely they are to work as a whole, we'd have to check edges of the graph multiple times, which doesn't preserve independence.

So instead, we will write our uniformly random graph $G$ as the union of graphs $G_0, G_1, \dots, G_{10 \log n}$, where $G_0$ contains each edge independently with probability $\frac14$, and $G_1, \dots, G_{10 \log n}$ contain each edge independently with probability $p$, chosen so that $\frac34(1-p)^{10 \log n} = \frac12$. Then the union will contain each edge with probability $\frac12$, so it will be the uniformly random graph. If we solve for $p$, we get $p = O(\frac{1}{\log n})$, but all we'll really need is for $p$ to be asymptotically bigger than $\frac{1}{\sqrt n}$.

Then I claim that:

  1. A greedy path chosen in $G_0$ will reach length $n - 5\log n$ with very high probability.
  2. Doing step 2 of the algorithm in any of the $G_1, \dots, G_{10 \log n}$ will work with very high probability.
  3. Doing step 3 of the algorithm in any of the $G_1, \dots, G_{10 \log n}$ will work with very high probability.

Then we can just look at graphs $G_0, G_1, \dots$ sequentially as we go through the algorithm. This preserves independence, and if the edges we need will be in the graph $G_i$ we're looking at, they will be in the union $G$.

For the first claim: the probability that a greedy path will get stuck while there's still $5 \log n$ vertices to pick from is $(\frac34)^{5\log n} = n^{-5\log \frac43}$, so the probability is at most $n^{1 - 5\log \frac43} \approx n^{-0.43}$ that it ever gets stuck.

For the second claim: we have at least $\frac n2$ options for vertices $v_i$ and $v_{i+1}$, and each one works with probability $p^2$. The probability that none of them work is $(1-p^2)^{n/2} \le e^{-p^2n/2}$, which approaches $0$ as $n\to \infty$. (This is where we want $p \gg \frac{1}{\sqrt n}$, so that the exponent goes to $-\infty$ as $n\to\infty$. We actually want a bit better than that, because we want all $O(\log n)$ of these steps to work, so the probability should go to $0$ faster than $\frac{1}{\log n}$. But our $p$ is actually quite a bit larger than $\frac{1}{\sqrt n}$, so we have that wiggle room.)

For the third claim: we have at least $\frac n2$ options for the vertex $v$, and each works with probability $p$. The probability that none of them work is $(1-p)^{n/2} \le e^{-pn/2}$, which approaches $0$ as $n\to \infty$.

$\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.