<p>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$. </p>

<p>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. </p>

CC BY-SA 2.5
2010-11-29T09:00:30.073Z
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.
JimN
CC BY-SA 2.5
2010-08-25T16:19:00.370Z
2010-08-25T16:19:00.370Z
Aaron Roth
<p>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.</p>

CC BY-SA 2.5
2010-08-25T15:44:47.180Z
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 ?
Suresh Venkat
CC BY-SA 2.5
2010-08-25T21:37:25.957Z
....and Noam answers that in the negative.
Suresh Venkat
CC BY-SA 2.5
2010-08-25T15:23:35.903Z
2010-08-25T15:23:35.903Z
Mohammad Al-Turkistany
<p>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.)</p>

CC BY-SA 2.5
2010-11-19T10:15:09.490Z
Are you assuming that the requested/assumed function runs in poly-time? If so, this was not originally requested. Maybe we can sample in super-poly-time?
Raphael
CC BY-SA 2.5
2010-11-19T15:33:11.653Z
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](http://portal.acm.org/citation.cfm?id=31202) that the polynomial hierarchy collapses
Peter Shor 
CC BY-SA 2.5
2010-08-25T17:16:15.723Z
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: http://cstheory.stackexchange.com/questions/562/how-to-produce-a-random-graph-that-does-not-have-a-hamiltonian-cycle/568#568
Ohad Kammar
CC BY-SA 2.5
2010-08-25T19:20:05.107Z
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.
Noam
CC BY-SA 2.5
2010-08-26T13:20:58.370Z
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).
Ohad Kammar
CC BY-SA 2.5
2010-08-27T23:47:14.293Z
@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.
Emil
CC BY-SA 2.5
2010-09-03T12:26:50.943Z
@Emil: You're right. I guess that "postivie fraction" can be rigourously formulated as "a polynomial time class of graphs".
Ohad Kammar
CC BY-SA 3.0
2010-08-25T16:04:35.920Z
2014-03-28T21:38:53.270Z
2014-03-28T21:38:53.270Z
Noam
<p>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.</p>

<p>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)</p>

CC BY-SA 2.5
2010-11-19T10:12:04.420Z
This is right but a uniform distribution was not requested (if maybe implied).
Raphael
CC BY-SA 2.5
2010-11-19T20:08:17.017Z
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.
Jagadish
CC BY-SA 2.5
2010-08-25T16:20:50.570Z
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.
Robin Kothari
<ds.algorithms><graph-theory>
How to produce a random graph that does not have a Hamiltonian cycle?
Jagadish
# How to produce a random graph that does not have a Hamiltonian cycle?

(Asked by: username_0 on 2010-08-25)

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)

**Tags:** ds.algorithms, graph-theory
> **Comments:**
> **username_2**: 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.  
> **username_1**: This is right but a uniform distribution was not requested (if maybe implied).  
> **username_0**: 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.  

---

## 3 answers

### Answer by username_7 on 2010-08-25. Score: 34 | Accepted answer

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.)

> **Comments:**
> **username_9**: 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: http://cstheory.stackexchange.com/questions/562/how-to-produce-a-random-graph-that-does-not-have-a-hamiltonian-cycle/568#568  
> **username_7**: 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.  
> **username_9**: 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).  
> **username_10**: @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.  
> **username_9**: @Emil: You're right. I guess that "postivie fraction" can be rigourously formulated as "a polynomial time class of graphs".  
> **username_1**: Are you assuming that the requested/assumed function runs in poly-time? If so, this was not originally requested. Maybe we can sample in super-poly-time?  
> **username_8**: 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](http://portal.acm.org/citation.cfm?id=31202) that the polynomial hierarchy collapses  

---

### Answer by username_3 on 2010-08-25. Score: 11

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.

> **Comments:**
> **username_4**: 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.  

---

### Answer by username_5 on 2010-08-25. Score: 1

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.

> **Comments:**
> **username_6**: 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 ?  
> **username_6**: ....and Noam answers that in the negative.  

---

