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 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 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).
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:
- 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,
- in general $G$ is not bipartite,
- 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 @orlp 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 @orlp 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.
