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)

Improve this question
$\endgroup$
3
  • 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
    Commented Aug 25, 2010 at 16:20
  • $\begingroup$ This is right but a uniform distribution was not requested (if maybe implied). $\endgroup$
    – Raphael
    Commented Nov 19, 2010 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
    Commented Nov 19, 2010 at 20:08

3 Answers 3

Reset to default
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.)

Improve this answer
$\endgroup$
7
  • 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
    Commented Aug 25, 2010 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
    Commented Aug 25, 2010 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
    Commented Aug 26, 2010 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
    Commented Aug 27, 2010 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
    Commented Nov 19, 2010 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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Nov 29, 2010 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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Aug 25, 2010 at 15:44
  • 5
    $\begingroup$ ....and Noam answers that in the negative. $\endgroup$
    – Suresh Venkat
    Commented Aug 25, 2010 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.