Matching

From Cophy
Jump to: navigation, search

Contents


Introduction

Matchings occur in many combinatorial optimization problems either as main problem or as a subroutine. We give a brief introduction to the theory of matching algorithms. For more detailed information, we refer the interested reader to [Lovász, Plummer (1986)] or [Cook et al. (1998)].

Definition

A matching in a (undirected) graph G = (V,E) is a set of edges M ⊆ E such that no vertex of G is incident to more than one edge of M.

M-covering

A vertex v ∈ V is M-covered if e = (v,w) ∈ M ⊆ E for some vertex w ∈ V, otherwise v is called M-exposed. Given a graph it is a well known problem to find a matching M with the minimum number of M-exposed vertices. We call a matching "maximum matching" if it is one of maximum cardinality, i.e. has the minimum number of M-exposed vertices.

The following Figure shows a matching with two M-exposed vertices. Note that it is not maximum as there exists an augmenting path connecting the two M-exposed vertices.

Matching pic 1.jpg


Another version of the matching problem arises when we are given weights on the edges (c(e) ∀ e ∈ E) and are asked to find a matching M that has largest total weight \scriptstyle c(M) = \sum\limits_{e \in M} c(e).

A matching is called perfect matching if all vertices are M-covered.


There exist different efficient algorithms solving these questions.
We will address some matching algorithms for bipartite graphs and for general graphs. The basic ideas for a bipartite matching algorithm date back at least to König in the 1930s. For the general case Tutte's Matching Theorem appeared in the 1940s, and approaches based on so called augmenting paths were suggested in the 1950s. However, finding an efficient, i.e. polynomial, algorithm for the matching problem on general graphs remained an elusive goal for a long time until Edmonds gave the first polynomial-time algorithm - the Blossom algorithm.

Alternating paths, augmenting paths, and alternating trees

We introduce some basic notations and give a short overview over the above mentioned algorithms.

Given a graph G = (V,E) and a matching MV we call a path π = v1v2, ..., vk alternating if each edge (vi,vi + 1) connects a vertex in the matching M with a vertex not in the matching V\M (note that edges are undirected). The path π is called augmenting if both endpoints v1 and vk are distinct and M-exposed.

Matching pic 2.jpg

In the above Figure an alternating but not augmenting path is shown.


Berge recognized the fundamental fact, that a matching M is maximum if and only if there is no augmenting path. This suggest a constructive approach for finding maximum matchings in a graph:

Repeatedly do the following. Find an augmenting path and obtain a new matching by removing the matched edges along the path from the matching and adding to it the formerly unmatched ones. Stop the procedure when no augmenting path can be found any more.

The notion of augmenting paths leads to the basic framework of matching algorithms, i.e. alternating trees.

Any even length alternating path starting and ending at some M-exposed vertices is an augmenting path with respect to the current matching M.

Suppose we have a matching M and an M-exposed vertex r. From this vertex we search for alternating paths in G. In doing so, we build two sets A,B of vertices, such that each vertex in set A is the end of an odd length alternating path beginning at vertex r. Clearly, set B is built of all vertices that are the end of an even length alternating path starting in r. This can be considered as a tree T rooted at vertex r of alternating paths. We denote by A(T) and B(T) the sets of vertices at odd and even (respectively) distance from the root r in T.

There is a simple condition under which one can conclude that G has no perfect matching. Call an alternating tree T with respect to a matching M frustrated if every edge of G having one end in B(T) has the other end in A(T). Now, if G has a matching M and an alternating tree T that is frustrated, then G has no perfect matching.

Matching in bipartite graphs

We are given a bipartite graph and ask for matchings.

Maximum matchings as well as minimum-weight perfect matchings in bipartite graphs can be solved via network flow techniques, cf. [Cook et al. (1998)]. Finding perfect matchings in bipartite graphs further can be solved by finding augmenting paths with respect to the current matching and augmenting the current matching by flipping the state of each edge, i.e. being part of the matching or not, along the path, cf. the following two Figures. On the left side an alternating (augmenting) path is found. Red edges belong to the matching. This path is then used in the augmenting step. The new matching is shown on the right.


This is summarized in the following pseudocode.


Algorithm 1: Perfect matching for bipartite graphs

  1. set M =
  2. choose M-exposed vertex r and put T = ({r}, ∅)
  3. while there exists (v,w) ∈ E with v ∈ B(T), w ∉ A(T) ∪ B(T)
    if w is M-exposed then
    • augment M
    if there is no M-exposed vertex then
    • stop with perfect matching M
    else
    • replace T by T = ({r}, ∅), where r is M-exposed
    else
    • extend T
    • stop G has no perfect matching


The algorithms stops either if a perfect matching is found or with the conclusion that the graph has no perfect matching.

Matching pic 3 1 and 3 2.jpg

Blossom algorithm for perfect matching

The task to determine a perfect matching in a general graph needs additional concepts. Especially the handling of odd cycles. In the bipartite case there was no need to worry about odd cycles as all cycles are of even length. Odd cycles make things harder to solve, as there exists no perfect matching in odd cycles. Edmonds came up with the idea to shrink odd cycles while still using alternating trees.

Shrinking odd cycles

Let C be an odd cycle in G and δ denotes all edges which are incident to (a set of) node(s). Define G' = G × C = (V',E'), where V' = V \ V(C) ∪ {c}, and E' = E \ δ(V(C)) ∪ {e' = (v,c) | ∃ e  = (v,w) ∈ Ew ∈ V(C), v ∉ V(C)}, as the subgraph obtained from G by shrinking C to a pseudo-vertex, see also the article shrinking of graphs.

Given a graph G' obtained by a sequence of odd-cylce shrinkings, then G' consists of two types of vertices, i.e. original vertices and pseudo-vertices. Again we have a criterion that tells us whether G has a perfect matching. Let G' be as before, let M' be a matching in G', and let T' be an alternating tree of G' such that no element of A(T) is a pseudo-vertex. If T is frustrated, then G has no perfect matching.

Next, we observe that if there exists an edge (v,w) with vw ∈ B(T), then this edge together with the path in T from v to w forms an odd cycle which can be shrunken, we call such an odd cycle blossom. Shrinking a blossom conserves the matching and the alternating tree structure in G'.

The procedure is summarized in Algorithm 2:

Algorithm 2: Perfect matching for general graphs

  1. set M = M' =
  2. set G' = G
  3. choose M'-exposed vertex r of G' and put T = ({r}, ∅)
  4. while there exists (v,w) ∈ E' with v ∈ B(T), w ∉ A(T)
    case w ∉ V(T) and w is M'-exposed
    • augment M'
    • extend M' to a matching M of G
    if there is no M'-exposed vertex in G'then
    • stop with perfect matching M'
    else
    • replace T by T = ({r}, ∅), where r is M'-exposed
    case w ∉ V(T) and w is M'-covered
    • extend T
    case w ∈ B(T)
    • shrink blossom and update M' and T
    • stop G has no perfect matching


We can use the Blossom algorithm to determine a maximum matching. If it terminates with a perfect matching then it is maximum. If it terminates with a matching and a frustrated tree T (G does not have a perfect matching), then we can get a matching M in G from the matching M' but it need not to be maximum. There may still exist augmenting paths in some parts of G. In this case we delete V(T) from G', and if any M' exposed vertex remains, we apply the Blossom algorithm to the new G' starting with the matching M'. Clearly, G' does not contain pseudo-vertices. We continue this procedure until there are no pseudo-vertices left. Finally we restore everything and get a maximum matching in G.

Minimum-weight perfect matchings

To answer the weighted matching questions one needs the above techniques and an optimality criterion that arises from linear programming.

We will not go into technical details. The algorithm for the minimum weight perfect matching problem in general graphs is a primal-dual algorithm. That is, with the help of duality theory of integer programming an optimum primal solution is obtained while simultaneously an optimum dual solution is found.

For more details, we refer the interested reader to [Cook et al. (1998)] and the references within. We want to mention that there exists freely available implementations solving the minimum weight perfect matching problem.

Nowadays the implementation of [Cook and Rohe (1999)], called Blossom IV, is one of the experimentally fastest implementation and widely spread. Recently a new implementation, called Blossom V, was presented by [Kolmogorov (2009)], that usually needs less computational time for solving the minimum weighted perfect matching problem.

Personal tools