28
$\begingroup$

Let class A denote all the graphs of size $n$ which have a Hamiltonian cycle. It is easy to produce a random graph from this class--take $n$ isolated nodes, add a random Hamiltonian cycle and then add edges randomly.

Let class B denote all the graphs of size $n$ which do not have a Hamiltonian cycle. How can we pick a random graph from this class? (or do something close to that)

$\endgroup$
  • 3
    $\begingroup$ How is it clear that the first procedure produce graphs uniformly at random? It's clear that it always produces Hamiltonian graphs, but since you're randomly adding edges later, you might introduce more Hamiltonian cycles, making some graphs appear more frequently than others. $\endgroup$ – Robin Kothari Aug 25 '10 at 16:20
  • $\begingroup$ This is right but a uniform distribution was not requested (if maybe implied). $\endgroup$ – Raphael Nov 19 '10 at 10:12
  • 1
    $\begingroup$ Yes, I don't care about uniformity. I would like to give every graph in the family of non-Hamiltonian graphs some chance of getting picked. The problem with uniform sampling is quite basic: AFAIK, we don't know how sample uniformly from a family of graphs of size n, let alone those with Hamiltonian cycles. $\endgroup$ – Jagadish Nov 19 '10 at 20:08
34
$\begingroup$

This is impossible (unless NP=coNP) since in particular that implies a poly-time function whose range is the non-Hamiltonian graphs (the function goes from the random string to the output graph), which in turn will imply an NP-proof of non-Hamiltonianicity (to prove G doesn't have an Hamiltonian circuit, show x that maps to it.)

$\endgroup$
  • 3
    $\begingroup$ You assume that such a function is on-to the class of non-Hamiltonian graphs. This is only the case if we want the distribution to be uniform. See also Aaron's comment below: cstheory.stackexchange.com/questions/562/… $\endgroup$ – Ohad Kammar Aug 25 '10 at 17:16
  • 5
    $\begingroup$ This does not assume anything about the probabilities of choosing each graph (like that it is uniform), only that the graphs that may be output by the algorithms are exactly the non-Hamiltonian ones (onto). If you allow error on either side, then indeed this may be possible. $\endgroup$ – Noam Aug 25 '10 at 19:20
  • 1
    $\begingroup$ I agree, it's not the uniformity of the distribution that matters, but rather the fact that all non-Hamiltonian graphs have non-zero probability. If even one of them has zero probability, your proof doesn't apply (without further knowledge on the support of the distribution). $\endgroup$ – Ohad Kammar Aug 26 '10 at 13:20
  • 1
    $\begingroup$ @Ohad: if one of them is missed out, then you can just add this to a look-up table. I think the problems only start if you miss out a positive fraction of them, but then you are not sampling uniformly. $\endgroup$ – Emil Aug 27 '10 at 23:47
  • 3
    $\begingroup$ If your algorithm produces a uniform distribution on the non-Hamiltonian graphs with probability $1-\epsilon$ and a Hamiltonian graph with probability $\epsilon$, and $\epsilon \rightarrow 0$ as the input size goes to $\infty$, then I think you should be able to combine this algorithm with random hash functions to find an constant-round interactive proof of non-Hamiltonicity. This would imply that the polynomial hierarchy collapses $\endgroup$ – Peter Shor Nov 19 '10 at 15:33
11
$\begingroup$

Bollobas, Fenner, and Frieze (http://portal.acm.org/citation.cfm?id=22145.22193) give a polynomial time algorithm for finding Hamiltonian cycles in random graphs, that has an error rate asymptotically tending to 0 in the size of the graph. If you wanted to generate n vertex graphs that were not Hamiltonian, you could select a random graph $G_{n,m}$ with $m$ such that the graph was Hamiltonian with constant probability bounded away from 1. You could then run the BFF algorithm to attempt to find a Hamiltonian cycle in it, and reject the graph if the algorithm succeeds. After a constant number of rounds, you would expect to find a graph for which the algorithm failed to find a Hamiltonian cycle, and although this graph might in fact be Hamiltonian, the probability of this will be diminishing in $n$.

Of course, this does not select uniformly at random from the set of all non-Hamiltonian $n$ vertex graphs, but it does select from an interesting subclass -- one for which you would expect a nontrivial fraction of graphs to be Hamiltonian, as well as a nontrivial fraction not.

$\endgroup$
  • $\begingroup$ This is a good idea, although we can skip the whole probabilistic algorithm for finding Ham cycle. The question does not ask that the sampling procedure runs in expected polytime or anything. So create a random graph from your favorite distribution, determine if it is Hamiltonian with some exact algorithm, and if it is Hamiltonian then discard it and repeat the process. If the distribution used was the uniform distribution over all labeled graphs, this will actually produce every non-Hamiltonian labeled graph with uniform probability. $\endgroup$ – JimN Nov 29 '10 at 9:00
1
$\begingroup$

The first task is easy because Hamiltonian graphs are easy to verify. However, There is no known short proof that can be efficiently verified to witness that given graph is non-Hamiltonian.

$\endgroup$
  • 1
    $\begingroup$ I think turkistany's answer brings up an interesting question. In general is it possible to sample uniformly from a language that's co-NP-complete ? $\endgroup$ – Suresh Venkat Aug 25 '10 at 15:44
  • 5
    $\begingroup$ ....and Noam answers that in the negative. $\endgroup$ – Suresh Venkat Aug 25 '10 at 21:37

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.