10
$\begingroup$

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

enter image description here

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

$\endgroup$
13
  • $\begingroup$ 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? $\endgroup$
    – holf
    May 26 at 14:45
  • $\begingroup$ 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? $\endgroup$
    – Alt-Tab
    May 27 at 14:29
  • 2
    $\begingroup$ 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. $\endgroup$ May 27 at 20:49
  • $\begingroup$ 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. $\endgroup$
    – holf
    May 28 at 7:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – orlp
    Jun 11 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.