Matching in Scientific Computing

Given a graph G, a matching M is a set of edges such that no two edges in M are incident on the same vertex. Matching is a fundamental combinatorial problem that has applications in many contexts: high-performance computing, bioinformatics, network switch design, web technologies, etc. Examples in the first context include sparse linear systems, where matchings are used to place large matrix elements on or close to the diagonal, block triangular decomposition, computing a sparse basis for the null space or column space of under-determined matrices, and multi-level graph partitioning algorithms where matchings are used in the coarsening phase. Click here for a compendium of applications of the matching problem, and here for a collection of reference material.

Based on the objective function, matching problems can be classified into:

1. Maximum (Cardinality) Matching: Maximize the number of edges in the matching.
2. Maximum (Edge) Weighted Matching: Maximize the sum of the weights of the matched edges.
3. Maximum (Vertex) Weighted Matching: Maximize the sum of the weights of the matched vertices.

Matchings in a bipartite graph are easier to compute than in general (or nonbipartite) graphs. Similarly, the unweighted versions are easier than the weighted versions of the matching problem. The weighted versions may also have additional restrictions on the cardinality of the matching, e.g., a maximum weight matching among all matchings of maximum cardinality.

Matching algorithms compute optimal solutions in polynomial time with the help of techniques like augmentation, blossoms and primal-dual formulations. However, these polynomial time algorithms can still be slow for many scientific computing applications. Approximation algorithms become important when matching needs to be computed a large number of times for a given application (for example, multi-level algorithms), for massive graphs, or in applications with resource limitations (for example, high-speed network switches that implement matching algorithms in hardware with severe restrictions on available memory and high performance requirements).

The need for parallel algorithms arise when matching needs to be computed on massive graphs, such as the ones arising from web applications, or  when the graph is predistributed on the processors of a parallel computer.

CSCAPES is currently developing parallel matching algorithms based on approximation techniques. Work on serial and exact algorithms has also been undertaken in the past. Our work has resulted in a 2/3-approximation to the maximum vertex-weight matching problem for bipartite graphs. Efficient implementations of the algorithms in C++ are available. Optimal and approximate solutions for all three kinds of matching problems, discussed above, are available in MatchBox (except weighted matching in nonbipartite graphs), and parallel implementations are available in MatchBoxP.

Software:

       MatchBox (Serial Code: Requires C++ Compiler)

       MatchBoxP (Parallel Code: Requires C++ Compiler and MPI toolkit; predistributed with Metis)

This software has not been released yet, but beta users could email the authors for a trial copy.

Members:

       Alex Pothen (apothen at purdue  dot edu)
       Florin Dobrian (dobrain at cs dot odu dot edu)
       Mahantesh Halappanavar (mhalappa at odu dot edu)

Presentations and Papers:
      Alex Pothen:

-                SIAM Conference on Discrete Mathematics, Burlington, VT, June 2008. A 2/3-approximation algorithm for vertex weighted matching in a bipartite graph.

      Florin Dobrian:

-                Parallel Matching algorithms (CSCAPES Workshop, Santa Fe, June 2008)

      Mahantesh Halappanavar:

-                Thesis Proposal  (Mahantesh Halappanavar, Thesis proposal, December 2007)

-                A parallel approximation matching algorithm (CSCAPES Seminar, September 2008)

Papers are currently being written.

Compendium of applications of the graph matching problem: Here

Collection of reference material on graph matching : Here

Last updated ... September 29, 2008.