[Lemon-user] recognize multiple perfect matchings?

[Alpár Jüttner]

On Tue, 2011-09-27 at 07:40 -0400, Zac Bullard wrote:
> Hello All,
> 
>    I am trying to identify which edges can be a part of perfect
> matching, given a graph that can hold multiple perfect matching sets.
> I can find the edges for one configuration, but not the other.


The easiest way is probably to check it for each edge (u,v) one-by-one,
as follows.

      * Remove nodes u and v from the graph. (It will remove the edge
        (u,v), too).
      * Look for a perfect matching in the remaining graph. If there
        exists, then edge (u,v) can be a member of a perfect matching in
        the original graph, otherwise it cannot.

An alternative approach is to use the weighted perfect matching
algorithm (lemon::MaxWeightedPerfectMatching) with an appropriate weight
function.

      * Let the weight of edge (u,v) be 1, and let the weight of all
        other edges be 0.
      * Thus, if the weight of the max weight prefect matching is 1,
        then (u,v) can be a member of a perfect matching, if it is 0,
        then it cannot.

This second approach is easier to implement, for it doesn't require
modifying (and restoring) the graph.

In theory, it is possible to find the set of the edges you are looking
for at once by running the weighted perfect matching algorithm on an
appropriately weighted full graph, then analyzing the provided dual
solution. This however needs a bit understanding of the so-called
"duality slackness condition", so please let us now if the approaches
above doesn't work for you, then I'll describe this, too.

Regards,
Alpár