*Learning objectives*

Algorithms from `mcb_matching.h` ,
`mwb_matching.h` ,
`mc_matching.h` , and
`mw_matching.h` |

The marriage problem |

Weighted and unweighted, bipartite, and general matchings |

In the *marriage
problem*, ladies and gentlemen willing to marry stand
vis-à-vis. Each lady may declare whom of the hopeful gentleman she
would potentially marry. In general, not each gentleman appeals to
each lady. Moreover, a certain surplus of ladies prevails by nature,
at least on the marriage market, but not on the exchanges that are
held in discotheques and similar locations; there, often a huge
surplus of gentlemen prevails. Figure 5.25
shows an instance of such a problem.

The problem now is to marry as many ladies as possible such that each lady gets a gentleman of her choice and that, of course, no two ladies are married to the same gentleman. It is understood that the problem may also be formulated vice-versa, from the gentlemen's viewpoint; but as it is in nature's nature, it is unfortunately the ladies that take the choice, not vice-versa. So mating as many ladies as possible is tantamount to mating as many gentlemen as possible. Therefore, we may introduce a little justice and formulate the problem such that each pair consisting of a lady and a gentleman may tell whether they want to marry or not. So the graph that underlies the problem is undirected; the direction of the edges is irrelevant.

An abstract formulation of the problem is the following: A
*matching* in a graph is
set M of edges with no no two edges having a node in common. A
*maximum matching*
is a maximal set with this property. A maximum matching always
exists; it does not have to be unique, however. Not all nodes have
to be matched in a maximum matching, see Figure 5.25; if indeed all nodes are matched,
the matching is called *perfect*.

This abstract problem definition has many concrete
manifestations. Another formulation is the *assignment problem*: On the
job market, a set of workers faces a set of open jobs, but not
each worker is appropriate for each job, and each worker may fill
at most one vacancy. As many workers as possible are to be engaged
according to their capabilities; conversely, as many vacancies as
possible are to be filled.

The (heterosexual) marriage problem is to find a maximum
matching in a bipartite graph. Often the marriage problem is
specified more precisely as the problem of finding a
*maximum bipartite, unweighted
matching*. Here “bipartite” stands for
the fact that the underlying graph is bipartite,
“unweighted” stands for the fact that the edges are
not labeled with weights, that is, that the pairs do not specify
how much an accomplished marriage would be worth to them. A
synonym is *maximum bipartite cardinality matching*.

LEDA offers some functions for computing maximum
bipartite matchings. All these functions are declared in the
header file
* mcb_matching.h*.

The function

list<edge> MAX_CARD_BIPARTITE_MATCHING(graph& G);

computes a maximum bipartite cardinality matching in a
graph `G`

. Precondition is that `G`

indeed is bipartite. The function
returns a list of the edges that form a maximum matching.

To clarify the usage of this function, we list the program that has been used to create Figure 5.25. With this program the user can edit a graph in a GraphWin; each time is pressed, a maximum matching is drawn, and the pairings of the matching are printed.

#include <LEDA/mcb_matching.h> #include <LEDA/basic_graph_alg.h> #include <LEDA/graph.h> #include <LEDA/graphwin.h> #include <LEDA/list.h> #include <LEDA/string.h> #include <iostream> using leda::GRAPH; using leda::edge; using leda::node; using leda::GraphWin; using leda::window; using leda::list; using leda::string; using std::cout; int main() { GRAPH<string,int> G; GraphWin gw(G, 500, 700, "Marriage Problem"); gw.set_node_shape(leda::rectangle_node); gw.set_node_label_type(leda::data_label); gw.set_node_width(100); gw.set_edge_direction(leda::undirected_edge); gw.set_flush(false); gw.display(window::center,window::center); while(gw.edit()) { if(!Is_Bipartite(G)) { gw.message("This graph is not bipartite! Click <done>."); gw.wait(); gw.del_message(); continue; } list<edge> L = MAX_CARD_BIPARTITE_MATCHING(G); // max. matching may have changed, so reset drawing to initial values gw.set_edge_width(1); gw.set_edge_color(leda::black); gw.set_node_border_color(leda::black); gw.set_node_border_width(1); gw.set_width(L, 3); gw.set_color(L, leda::red); cout << "\nThe following is a maximum cardinality matching:\n"; edge e; forall(e, L) { node person1 = G.source(e); node person2 = G.target(e); cout << G.inf(person1) << " marries " << G.inf(person2) << "\n"; gw.set_border_color(person1, leda::red); gw.set_border_color(person2, leda::red); gw.set_border_width(person1, 3); gw.set_border_width(person2, 3); } gw.redraw(); } }

The program outputs the following:

The following is a maximum cardinality matching: Claudia marries Michael Bettina marries Bernd Roxane marries Wolfram Sibylle marries Volker Sabine marries Joerg Marion marries Uwe

“Honey, I bet // that you gonna get // your man before you die” (Rolling Stones.)

If, in the marriage problem, each pair additionally may specify how much an accomplished marriage would be worth to it, the edges in the underlying graph carry weights. (Another view is the one of a marriage agency that obtains a certain amount of money for each accomplished marriage.)

Then the problem is to find a matching in which the
sum of the edge weights of the matching is
maximal. (Then the marriage agency makes as much money as
possible out of the matching.) This is called a
*maximum bipartite, weighted matching*.

LEDA keeps ready some functions for this; they all are declared in the
header file * mwb_matching.h*. For example,

list<edge> MAX_WEIGHT_BIPARTITE_MATCHING(graph& G, edge_array<int> weight);

computes a maximum bipartite, weighted matching on the graph
`G`

. Here the weights of the edges are given by the
edge array `weight`

. `G`

must be
bipartite.

Since the sexual revolution in the 60s, bipartite graphs go more and more out of fashion for representing marriage problems. Today we live in a society that admits also same-sex marriages. This means for the underlying graph that now the edges do not exhibit a strict separation of their nodes into female and male ones any more; in fact, it may be any graph. The nodes in it have just one sex only or are to be regarded as sexless; everyone may gallivant with everyone, ladies with ladies, ladies with gentlemen, and gentlemen with gentlemen.

This sexually neutral marriage problem, which has an
arbitrary graph underlying, is called the problem to find a
*maximum general, unweighted matching*. A
synonym for this is *maximum general cardinality
matching*.

LEDA offers some functions for this; they all are declared in the
header file * mc_matching.h*. For example,

list<edge> MAX_CARD_MATCHING(graph& G);

computes a maximum general cardinality matching on the graph `G`

.

The most general case, which includes the previously
described cases, is the one of an arbitrary graph whose edges
are provided with weights. Here a matching that maximizes the
sum of the edge weights of the matching edges is called a
*maximum general, weighted matching*. Figure 5.26 shows such a
matching.

Formulated as a marriage problem, both heterosexual and homosexual marriages are allowed here (in other words, the separation into two sexes is not made at all), and each pair specifies how much an accomplished marriage would be worth to it.

Also for this problem, LEDA offers some functions, which
all are declared in the header file
* mw_matching.h*. For
example,

list<edge> MAX_WEIGHT_MATCHING(graph& G, edge_array<int> weight);

computes a general, weighted matching on the graph `G`

. Here the weights
of the edges are given by the edge array `weight`

; they all have to be
non-negative.

All functions from `mw_matching.h`

have
the precondition that the underlying
`graph`

be connected and simple and have
neither self-loops nor reverse edges.

To clarify the usage of the function
`MAX_WEIGHT_MATCHING()`

, we list the program
that has been used to create Figure 5.26. With this
program, the user can edit a graph in a GraphWin; each time
is pressed, a maximum matching is
drawn, and the pairings of the matching are printed.

#include <LEDA/mw_matching.h> #include <LEDA/graph.h> #include <LEDA/edge_array.h> #include <LEDA/graphwin.h> #include <LEDA/list.h> #include <LEDA/string.h> #include <iostream> using leda::GRAPH; using leda::edge_array; using leda::edge; using leda::node; using leda::GraphWin; using leda::window; using leda::list; using leda::string; using std::cout; int main() { GRAPH<string,int> G; GraphWin gw(G, 500, 700, "Maximum General Weighted Matching"); gw.set_node_shape(leda::rectangle_node); gw.set_node_label_type(leda::data_label); gw.set_node_width(100); gw.set_edge_direction(leda::undirected_edge); gw.set_edge_label_type(leda::data_label); gw.set_flush(false); gw.display(window::center,window::center); while(gw.edit()) { edge_array<int> weight(G); edge e; forall_edges(e,G) weight[e] = G.inf(e); list<edge> L = MAX_WEIGHT_MATCHING(G, weight); // max. matching may have changed, so reset drawing to initial values gw.set_edge_width(1); gw.set_edge_color(leda::black); gw.set_node_border_color(leda::black); gw.set_node_border_width(1); gw.set_width(L, 3); gw.set_color(L, leda::red); cout << "\nThe following is a maximum weighted matching:\n"; int weight_of_matching = 0 ; forall(e, L) { weight_of_matching += weight[e]; node person1 = G.source(e); node person2 = G.target(e); cout << G.inf(person1) << " marries " << G.inf(person2) << "\n"; gw.set_border_color(person1, leda::red); gw.set_border_color(person2, leda::red); gw.set_border_width(person1, 3); gw.set_border_width(person2, 3); } cout << "The weight of this matching is " << weight_of_matching; cout << "\n"; gw.redraw(); } }

The output of the program for the graph from Figure 5.26 is:

The following is a maximum weighted matching: Anja marries Mick Ulli marries Keith Charlie marries August Brian marries Bill Claudia marries Herbert Bettina marries Sibylle Stefan marries Klaus Heinz marries Robert The weight of this matching is 144

Of course, one always gets along with the functions from
`mw_matching.h`

, which handle the most
general case and thus include all other cases. (For example, to
compute a maximum cardinality matching with one of these functions, all edge weights
could be set to 1.) The functions presented here strongly differ
by their running times, though. The more special the case is that
they handle, the faster are their implementations.

`MAX_WEIGHT_MATCHING()`

takes time
O(n·m·log(n)),
`MAX_CARD_MATCHING()`

only
O(n·m·a(n,m)), with a() being the *inverse Ackermann
function*, a function that is so small even for
extremely large n and m that, in practice, it may be regarded as
constant.

`MAX_WEIGHT_BIPARTITE_MATCHING()`

takes
time O(n·(m+n·log(n))). The running time of
`MAX_CARD_BIPARTITE_MATCHING()`

is
O(sqrt(n)·m) in the worst case; for a random graph, its
expected running time is O(m·log(n)).

More information about these functions can be found on the
corresponding manual pages of
`mcb_matching.h`

,
`mwb_matching.h`

,
`mc_matching.h`

, and
`mw_matching.h`

.

These pages also describe functions for computing a perfect matching in a graph (if there is one).