13
$\begingroup$

Suppose I have a graph $G$ with $M(G)$ the (unknown) set of perfect matchings of $G$. Suppose this set is non-empty, then how difficult is it to sample uniformly at random from $M(G)$? What if I am okay with a distribution that is close to uniform, but not quite uniform, then is there an efficient algorithm?

$\endgroup$
  • $\begingroup$ Do you know anything more about $G$? Or in other words, would you even be interested in any restricted graph classes? $\endgroup$ – Juho Mar 25 '13 at 1:16
  • $\begingroup$ @Juho I prefer results for general graphs, in particular for dense graphs (so what Yuval mentions in his answer seems promising). I have seen some results for planar graphs before, I think. However, since this is a general question, if you have an answer for some interesting families of graphs then it is probably still worthwhile to answers since others that search for this question might like to know. $\endgroup$ – Artem Kaznatcheev Mar 25 '13 at 17:47
  • $\begingroup$ Just to be clear, I assume you don't have $M(G)$ at hand? $\endgroup$ – Raphael Mar 25 '13 at 19:20
  • $\begingroup$ @Raphael I think the question would be trivial if you did. In fact I think the question would be relatively straightforward if you just had $|M(G)|$, since there is usually a correspondence between counting and sampling. Or did you mean "at hand" in some other way? $\endgroup$ – Artem Kaznatcheev Mar 26 '13 at 0:42
  • $\begingroup$ I see. I found your phrasing ambiguous, which I tried to correct. Did I get it right? $\endgroup$ – Raphael Mar 26 '13 at 10:13
8
$\begingroup$

There is a classical paper of Jerrum and Sinclair (1989) on sampling perfect matchings from dense graphs. Another classical paper of Jerrum, Sinclair and Vigoda (2004; pdf) discusses sampling perfect matchings from bipartite graphs.

Both these papers uses rapidly mixing Markov chains, and so the samples are only almost uniform. I imagine that uniform sampling is difficult.

$\endgroup$
1
$\begingroup$

If you assume that your graph is planar, then there is a polynomial time procedure for this sampling problem.

First, the problem of counting the number of perfect matchings is in P for planar graphs. ( https://en.wikipedia.org/wiki/FKT_algorithm ) ( A good exposition of this fact can be found in the first chapter of Jerrum's book on Counting, Sampling and Integrating.)

Next, for each edge $e$ of $G$, count the number of perfect matchings of $G \setminus e$. This can be turned into the probability that a uniform perfect matching contains $e$ - just divide by the number of perfect matchings in $G$. Sample an edge according to this probability, and continue inductively.

(This is taking advantage of the fact that matchings are a "self-reducible" structure, so counting problems and uniform sampling problems are essentially the same. You can see JVV "Random Generation of Combinatorial Structures from a Uniform Distribution" for more on this point of view.)

A simple proof that this gives the correct distribution:

Let $c(H)$ denote the number of ordered perfect matchings in a graph $H$, as ordered sequences. (Which is $n!$ times the number of unordered perfect matchings, $n = H/2$.)

Let $e_1, \ldots, e_n$ the sequence of edges chosen in this procedure. Since each step was independent of the former, the probability of choosing this sequence of edges is:

$\frac{ c(G \setminus e_1)}{c(G)} \frac{ c(G \setminus \{e_1, e_2\} )}{c(G \setminus e_1)} \ldots \frac{ c(G \setminus \{e_1, \ldots, e_{n-1} \}) }{c(G \setminus \{ e_1, \ldots, e_{n-2} \} )}$.

Note that $c(G \setminus \{e_1, \ldots, e_{n-1} \}) = 1$, since $G \setminus \{e_1, \ldots, e_{n-1} \}$ is just the edge $e_n$. So this product telescopes and leaves $1 / c(G)$.

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