<p><strong>Problem:</strong> Suppose that we have a graph <span class="math-container">$ G $</span> which admits at least one perfect matching. I would like to know if there is an algorithm that allows to find any perfect matching of this graph uniformly at random in polynomial-time.</p>
<p>It seems from this discussion: <a href="https://cstheory.stackexchange.com/questions/37163/complexity-of-uniform-generation-of-perfect-matchings">Complexity of Uniform Generation of Perfect Matchings</a> that the general problem is open. However, the structure of this graph is very specific, so maybe there is a way to address adequately this question (I describe the structure of the graph below).</p>
<p><strong>Motivation:</strong> in <a href="https://onlinelibrary.wiley.com/doi/pdf/10.1002/(SICI)1098-2418(199907)14:4%3C293::AID-RSA1%3E3.0.CO;2-G?casa_token=NXB30ZyimHQAAAAA:3MDLGM8paXF6rZjNZ3b-rdqM0qdU_nrL57SLkYVy7tbWmDPfRHHsmBbqBFxKWwzzBTp3xGcpc_s3eVA" rel="nofollow noreferrer">this reference</a> by Kannan et al. (1999), the authors propose a way to transform the problem of finding a random graph with a given degree sequence into finding a perfect matching of a graph built from the degree sequence using some gadgets.
Finding a polynomial solution to the perfect matching problem would give us a way to find a polynomial solution to finding a random graph with a given degree sequence.</p>
<p><strong><span class="math-container">$G$</span> structure:</strong> graph <span class="math-container">$G$</span> is built in the following way. Suppose you have a graphic degree sequence <span class="math-container">$(d_1,...,d_n)$</span>, consider a complete graph with <span class="math-container">$n$</span> nodes, then</p>
<ul>
<li>replace each edge <span class="math-container">$(u,v)$</span> by a path <span class="math-container">$ (u,e_{uv},e_{vu},v) $</span>,</li>
<li>with <span class="math-container">$d_u$</span> the degree of <span class="math-container">$u$</span>, replace each vertex <span class="math-container">$u$</span> by <span class="math-container">$ (n-1-d_u) $</span> &quot;mini-vertices&quot; <span class="math-container">$u_1,...,u_{n-1-d_u}$</span> and connect each mini-vertex to all <span class="math-container">$ e_{uv} $</span>,</li>
<li>the resulting graph is <span class="math-container">$G$</span>.</li>
</ul>
<p>For instance, supposing vertex <span class="math-container">$a$</span> is such that <span class="math-container">$(n-1-d_a) = 4$</span>, vertex <span class="math-container">$b$</span> is such that <span class="math-container">$(n-1-d_b) = 3$</span> and vertex <span class="math-container">$c$</span> is such that <span class="math-container">$(n-1-d_c) = 2$</span> then edges <span class="math-container">$ (a,b) $</span> and <span class="math-container">$ (a,c) $</span> would be transformed as in the figure below (for the sake of readability I only represent the transformation of these two edges).</p>
<p><a href="https://i.sstatic.net/90iMl.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/90iMl.png" alt="enter image description here" /></a></p>
<p>It can be checked that finding a perfect matching in <span class="math-container">$G$</span> is equivalent to finding a simple graph with the degree sequence <span class="math-container">$(d_1,...,d_n)$</span>: if the edge <span class="math-container">$ (e_{uv},e_{vu}) $</span> belongs to the perfect matching in <span class="math-container">$G$</span>, vertices <span class="math-container">$u$</span> and <span class="math-container">$v$</span> are connected in the graph with degree sequence <span class="math-container">$(d_1,...,d_n)$</span>, otherwise they are not.</p>
<p><strong>Additional remarks:</strong></p>
<ol>
<li>having a graphic degree sequence implies that at least one graph satisfies the degree sequence in the original problem, thus a perfect matching of <span class="math-container">$G$</span> exists,</li>
<li>in general <span class="math-container">$G$</span> is not bipartite,</li>
<li>it is possible to solve the problem of finding a random graph with a given degree sequence using an appropriate Monte Carlo Markov Chain sampling method, thus it is also possible for the perfect matching problem. However, there is no easy bound to the convergence time of the algorithm, so we want to avoid this type of sampling algorithm.</li>
</ol>
<p><strong>Edit:</strong></p>
<p>Following the discussion with @orlp I am editing to add a possible way to sample uniformly perfect matching in our specific context.</p>
<p><em>Unfortunately, this does not work for the reasons discussed in italic below</em></p>
<p>First, notice a few specificities of a perfect matching in the graph considered (not obvious at first sight, but I think they are true). I follow the notations given above:</p>
<ul>
<li>a perfect matching has exactly <span class="math-container">$ (n-1-d_a) $</span> edges of the type <span class="math-container">$ (a_i,e_{ax}) $</span> for a node <span class="math-container">$a$</span> of degree <span class="math-container">$d_a$</span>,</li>
<li>a perfect matching has exactly <span class="math-container">$d_a$</span> edges of the type <span class="math-container">$ (e_{ax},e_{xa}) $</span>,</li>
<li>note also that if we set all <span class="math-container">$ (a_i,e_{ax}) $</span> edges in a perfect matching, there is no liberty concerning the <span class="math-container">$ (e_{ax},e_{xa}) $</span> edges in the perfect matching.</li>
</ul>
<p>So let's consider the following weighting scheme, in the spirit of the discussion below. Let <span class="math-container">$k$</span> be the size of a perfect matching:</p>
<ul>
<li>edges of the form <span class="math-container">$ (e_{ax},e_{xa}) $</span> are all weighted with a weight <span class="math-container">$k$</span> (so that there weight has no influence on the maximum weight matching),</li>
<li>edges of the form <span class="math-container">$ (a_i,e_{ax}) $</span> are weighted with a weight <span class="math-container">$ k+U(0,1)$</span>, where <span class="math-container">$ U(0,1) $</span> is the uniform distribution between <span class="math-container">$0$</span> and <span class="math-container">$1$</span>,</li>
<li>with an argument similar to the one developed by @orlp we have that the maximum weight matching necessarily has <span class="math-container">$ k $</span> edges too,</li>
<li>moreover, we can check that all the perfect matchings in the unweighted graph are weighted according to a similar probability distribution (based on the description of the perfect matchings above, they have the same number of edges, weighted in a similar way).</li>
</ul>
<p><em>Perfect matchings of the unweighted graph do not all have the same probability of being the maximum weight matching according to this weighting process.
Indeed, when an edge <span class="math-container">$ (a_i,e_{ax}) $</span> connected to the minivertex <span class="math-container">$ a_i $</span> is in the matching, it implies that an edge <span class="math-container">$ (e_{xa},x_j) $</span> must be in the matching too and that nodes <span class="math-container">$a$</span> and <span class="math-container">$x$</span> are not connected in the resulting graph.
Consequently, the number of possible matchings involving minivertices <span class="math-container">$x_k$</span> is affected by what happened with minivertices <span class="math-container">$a_k$</span>.
We can check experimentally that the process does not give the same probability to all matchings, the sampling is not uniform.</em></p>

CC BY-SA 4.0
2021-05-26T14:45:07.540Z
I am not 100% sure I get the transformation. How are "mini-vertices" $u_i$s connected to $v_j$s? My first biased take on the problem would be to prove that $G$ has bounded clique-width and use this fact to sample exactly. Have you look into this direction?
holf
CC BY-SA 4.0
2021-05-27T14:29:16.823Z
I think the simplest way to answer your question is to draw a picture to explain the transformation. I have added one in the description of the problem.
Concerning clique-width no, I didn't look into this direction. Actually I am not familiar at all with the concept of clique-width, in what sense do you think it can be useful here?
Alt-Tab
CC BY-SA 4.0
2021-05-27T20:49:57.890Z
The link discussing the sampling problem for perfect matchings being open is saying that it is open as far as approximate counting is concerned. We know approximate sampling can be done for bipartite graphs but not yet for general graphs. Sampling exactly is #P-hard even in bipartite graphs.
Chandra Chekuri
CC BY-SA 4.0
2021-05-28T07:51:25.873Z
Thanks, this is helpful. It is indeed what I had in mind but now, I think I was too optimistic and this does not look like it has bounded cw. As I said, I was biased in this approach as it is part of my main toolbox. One can transform queries on bounded cw graphs into datastructures allowing to solve some pb easily, e.g. sampling vertex covers uniformely. Since you were transforming a clique, it triggered my reflexes but I am not sure it is a promising approach anymore.
holf
CC BY-SA 4.0
2021-05-29T13:05:52.093Z
@holf Ok, thanks for the suggestion in any case.
Alt-Tab
CC BY-SA 4.0
2021-05-29T13:18:08.017Z
@ChandraChekuri Yes indeed, that's what I understood too from the [related post](https://cstheory.stackexchange.com/questions/37163/complexity-of-uniform-generation-of-perfect-matchings). That's why I have also pointed out the fact that the graph is **not bipartite** as if it was the case, we could use Jerrum-Sinclair-Vigoda algorithm according to user Heng Guo.
Alt-Tab
CC BY-SA 4.0
2021-06-11T00:10:47.920Z
Assign to each edge in the graph a random weight $w_i \sim |G|/2 + U(0, 1)$. Then find the maximum weight matching.

This matching must be perfect, as the maximum possible weight of a matching with $|G|/2 - 1$ edges or fewer is $(|G|/2 - 1)(|G|/2 + 1) = |G|^2/4 - 1$, and the minimum possible weight of a perfect matching is $|G|^2/4$.

I don't see why the above wouldn't be uniformly random, but I also don't have a formal proof so I'm probably overlooking something.
orlp
CC BY-SA 4.0
2021-06-14T09:30:37.923Z
@orlp I think I understand your reasoning, which is very interesting. I am not sure about the details though. What does $|G|$ means for you? is it the number of edges of $G$ (say $m$)? or is it the size of a perfect matching in $G$ (say $k$)? I suppose it's the second which seems more promising. In that case, the weight of your maximum weighted matching must be larger than $k(k/2)$, taking the perfect matching in $G$ weighted by the minimum weight of each edge, as it is impossible to reach this value with less than $k$ edges then the weighted matching must have $k$ edges.
Is it what you mean?
Alt-Tab
CC BY-SA 4.0
2021-06-14T10:33:42.380Z
@Alt-Tab Sorry, $|G|$ is supposed to mean the number of nodes, I should've clarified that. A perfect matching will then always have exactly $|G|/2$ edges. And yes, the point of the setup is that in those conditions the maximum matching always is a perfect one as well.
orlp
CC BY-SA 4.0
2021-06-14T13:47:34.753Z
@orlp Ah of course, $ |G| $ is the number of nodes, so $ k=|G|/2$ with my notations. Then we can use something like the [blossom algorithm](https://en.wikipedia.org/wiki/Blossom_algorithm) to find this maximal matching in polynomial time, that's nice! Now, remains the question "is this matching uniform random in $G$?" I am not sure, I have to think more about this but that's already a good lead!
Alt-Tab
CC BY-SA 4.0
2021-06-14T14:09:50.780Z
Unfortunately, while my proposed scheme has a non-zero chance of selecting any perfect matching, it is not uniform. Consider the hypothetical scenario where there are three perfect matchings: two of them share all the same edges (and thus random variables) except a constant amount, whereas the third one doesn't share any with the other two and is thus completely uncorrelated to them. Then the distribution won't be a fair 1/3 for all of them, but rather approach 1/2, 1/4, 1/4. This is just a simple counterexample I [simulated](https://gist.github.com/orlp/9baf4cc7bae607291629b8651b88cf9f).
orlp
CC BY-SA 4.0
2021-06-15T13:22:01.073Z
@orlp Your counter-example is relevant, however I wouldn't reject the approach immediately in the context of this problem. If you look at the structure of the graph here, the structure around a $ (x_{uv},y_{uv}) $ edge is quite similar from an edge $(x_{uv},y_{uv}) $ to another $(x_{u'v'},y_{u'v'})$ (the only thing that changes is the number of mini-vertices connected to it). That makes me think that there might be a weighting scheme of the matching obtained which allows to balance the sampling... Not sure at all though...
Alt-Tab
CC BY-SA 4.0
2021-06-27T12:54:57.863Z
I have added an edit on the original problem following this discussion. @orlp I would be interested to have your thoughts about it.
Alt-Tab
<graph-algorithms><matching><sampling>
Finding uniformly random perfect matching of a graph
Alt-Tab
# Finding uniformly random perfect matching of a graph

(Asked by: username_0 on 2021-05-25)

**Problem:** Suppose that we have a graph $ G $ which admits at least one perfect matching. I would like to know if there is an algorithm that allows to find any perfect matching of this graph uniformly at random in polynomial-time.

It seems from this discussion: [Complexity of Uniform Generation of Perfect Matchings](https://cstheory.stackexchange.com/questions/37163/complexity-of-uniform-generation-of-perfect-matchings) that the general problem is open. However, the structure of this graph is very specific, so maybe there is a way to address adequately this question (I describe the structure of the graph below).

**Motivation:** in [this reference](https://onlinelibrary.wiley.com/doi/pdf/10.1002/(SICI)1098-2418(199907)14:4%3C293::AID-RSA1%3E3.0.CO;2-G?casa_token=NXB30ZyimHQAAAAA:3MDLGM8paXF6rZjNZ3b-rdqM0qdU_nrL57SLkYVy7tbWmDPfRHHsmBbqBFxKWwzzBTp3xGcpc_s3eVA) by Kannan et al. (1999), the authors propose a way to transform the problem of finding a random graph with a given degree sequence into finding a perfect matching of a graph built from the degree sequence using some gadgets.
Finding a polynomial solution to the perfect matching problem would give us a way to find a polynomial solution to finding a random graph with a given degree sequence.

**$G$ structure:** graph $G$ is built in the following way. Suppose you have a graphic degree sequence $(d\_1,...,d\_n)$, consider a complete graph with $n$ nodes, then

* replace each edge $(u,v)$ by a path $ (u,e\_{uv},e\_{vu},v) $,
* with $d\_u$ the degree of $u$, replace each vertex $u$ by $ (n-1-d\_u) $ "mini-vertices" $u\_1,...,u\_{n-1-d\_u}$ and connect each mini-vertex to all $ e\_{uv} $,
* the resulting graph is $G$.

For instance, supposing vertex $a$ is such that $(n-1-d\_a) = 4$, vertex $b$ is such that $(n-1-d\_b) = 3$ and vertex $c$ is such that $(n-1-d\_c) = 2$ then edges $ (a,b) $ and $ (a,c) $ would be transformed as in the figure below (for the sake of readability I only represent the transformation of these two edges).

[![enter image description here](https://i.sstatic.net/90iMl.png)](https://i.sstatic.net/90iMl.png)

It can be checked that finding a perfect matching in $G$ is equivalent to finding a simple graph with the degree sequence $(d\_1,...,d\_n)$: if the edge $ (e\_{uv},e\_{vu}) $ belongs to the perfect matching in $G$, vertices $u$ and $v$ are connected in the graph with degree sequence $(d\_1,...,d\_n)$, otherwise they are not.

**Additional remarks:**

1. having a graphic degree sequence implies that at least one graph satisfies the degree sequence in the original problem, thus a perfect matching of $G$ exists,
2. in general $G$ is not bipartite,
3. it is possible to solve the problem of finding a random graph with a given degree sequence using an appropriate Monte Carlo Markov Chain sampling method, thus it is also possible for the perfect matching problem. However, there is no easy bound to the convergence time of the algorithm, so we want to avoid this type of sampling algorithm.

**Edit:**

Following the discussion with @username_3 I am editing to add a possible way to sample uniformly perfect matching in our specific context.

*Unfortunately, this does not work for the reasons discussed in italic below*

First, notice a few specificities of a perfect matching in the graph considered (not obvious at first sight, but I think they are true). I follow the notations given above:

* a perfect matching has exactly $ (n-1-d\_a) $ edges of the type $ (a\_i,e\_{ax}) $ for a node $a$ of degree $d\_a$,
* a perfect matching has exactly $d\_a$ edges of the type $ (e\_{ax},e\_{xa}) $,
* note also that if we set all $ (a\_i,e\_{ax}) $ edges in a perfect matching, there is no liberty concerning the $ (e\_{ax},e\_{xa}) $ edges in the perfect matching.

So let's consider the following weighting scheme, in the spirit of the discussion below. Let $k$ be the size of a perfect matching:

* edges of the form $ (e\_{ax},e\_{xa}) $ are all weighted with a weight $k$ (so that there weight has no influence on the maximum weight matching),
* edges of the form $ (a\_i,e\_{ax}) $ are weighted with a weight $ k+U(0,1)$, where $ U(0,1) $ is the uniform distribution between $0$ and $1$,
* with an argument similar to the one developed by @username_3 we have that the maximum weight matching necessarily has $ k $ edges too,
* moreover, we can check that all the perfect matchings in the unweighted graph are weighted according to a similar probability distribution (based on the description of the perfect matchings above, they have the same number of edges, weighted in a similar way).

*Perfect matchings of the unweighted graph do not all have the same probability of being the maximum weight matching according to this weighting process.
Indeed, when an edge $ (a\_i,e\_{ax}) $ connected to the minivertex $ a\_i $ is in the matching, it implies that an edge $ (e\_{xa},x\_j) $ must be in the matching too and that nodes $a$ and $x$ are not connected in the resulting graph.
Consequently, the number of possible matchings involving minivertices $x\_k$ is affected by what happened with minivertices $a\_k$.
We can check experimentally that the process does not give the same probability to all matchings, the sampling is not uniform.*

**Tags:** graph-algorithms, matching, sampling

> **Comments:**
> **username_1**: I am not 100% sure I get the transformation. How are "mini-vertices" $u_i$s connected to $v_j$s? My first biased take on the problem would be to prove that $G$ has bounded clique-width and use this fact to sample exactly. Have you look into this direction?  
> **username_0**: I think the simplest way to answer your question is to draw a picture to explain the transformation. I have added one in the description of the problem. Concerning clique-width no, I didn't look into this direction. Actually I am not familiar at all with the concept of clique-width, in what sense do you think it can be useful here?  
> **username_2**: The link discussing the sampling problem for perfect matchings being open is saying that it is open as far as approximate counting is concerned. We know approximate sampling can be done for bipartite graphs but not yet for general graphs. Sampling exactly is #P-hard even in bipartite graphs.  
> **username_1**: Thanks, this is helpful. It is indeed what I had in mind but now, I think I was too optimistic and this does not look like it has bounded cw. As I said, I was biased in this approach as it is part of my main toolbox. One can transform queries on bounded cw graphs into datastructures allowing to solve some pb easily, e.g. sampling vertex covers uniformely. Since you were transforming a clique, it triggered my reflexes but I am not sure it is a promising approach anymore.  
> **username_0**: @username_1 Ok, thanks for the suggestion in any case.  
> **username_0**: @ChandraChekuri Yes indeed, that's what I understood too from the [related post](https://cstheory.stackexchange.com/questions/37163/complexity-of-uniform-generation-of-perfect-matchings). That's why I have also pointed out the fact that the graph is **not bipartite** as if it was the case, we could use Jerrum-Sinclair-Vigoda algorithm according to user Heng Guo.  
> **username_3**: Assign to each edge in the graph a random weight $w_i \sim |G|/2 + U(0, 1)$. Then find the maximum weight matching.  This matching must be perfect, as the maximum possible weight of a matching with $|G|/2 - 1$ edges or fewer is $(|G|/2 - 1)(|G|/2 + 1) = |G|^2/4 - 1$, and the minimum possible weight of a perfect matching is $|G|^2/4$.  I don't see why the above wouldn't be uniformly random, but I also don't have a formal proof so I'm probably overlooking something.  
> **username_0**: @username_3 I think I understand your reasoning, which is very interesting. I am not sure about the details though. What does $|G|$ means for you? is it the number of edges of $G$ (say $m$)? or is it the size of a perfect matching in $G$ (say $k$)? I suppose it's the second which seems more promising. In that case, the weight of your maximum weighted matching must be larger than $k(k/2)$, taking the perfect matching in $G$ weighted by the minimum weight of each edge, as it is impossible to reach this value with less than $k$ edges then the weighted matching must have $k$ edges. Is it what you mean?  
> **username_3**: @username_0 Sorry, $|G|$ is supposed to mean the number of nodes, I should've clarified that. A perfect matching will then always have exactly $|G|/2$ edges. And yes, the point of the setup is that in those conditions the maximum matching always is a perfect one as well.  
> **username_0**: @username_3 Ah of course, $ |G| $ is the number of nodes, so $ k=|G|/2$ with my notations. Then we can use something like the [blossom algorithm](https://en.wikipedia.org/wiki/Blossom_algorithm) to find this maximal matching in polynomial time, that's nice! Now, remains the question "is this matching uniform random in $G$?" I am not sure, I have to think more about this but that's already a good lead!  
> **username_3**: Unfortunately, while my proposed scheme has a non-zero chance of selecting any perfect matching, it is not uniform. Consider the hypothetical scenario where there are three perfect matchings: two of them share all the same edges (and thus random variables) except a constant amount, whereas the third one doesn't share any with the other two and is thus completely uncorrelated to them. Then the distribution won't be a fair 1/3 for all of them, but rather approach 1/2, 1/4, 1/4. This is just a simple counterexample I [simulated](https://gist.github.com/username_3/9baf4cc7bae607291629b8651b88cf9f).  
> **username_0**: @username_3 Your counter-example is relevant, however I wouldn't reject the approach immediately in the context of this problem. If you look at the structure of the graph here, the structure around a $ (x_{uv},y_{uv}) $ edge is quite similar from an edge $(x_{uv},y_{uv}) $ to another $(x_{u'v'},y_{u'v'})$ (the only thing that changes is the number of mini-vertices connected to it). That makes me think that there might be a weighting scheme of the matching obtained which allows to balance the sampling... Not sure at all though...  
> **username_0**: I have added an edit on the original problem following this discussion. @username_3 I would be interested to have your thoughts about it.  

---

## 0 answers

