Maximum Weight Matchings in Non-Bipartite Graphs

Maximum Weight Matchings in Non-Bipartite Graphs

I have four questions concerning algorithms for maximum weight
matchings in non-bipartite graphs.  (A matching is a selection of
edges from an undirected graph such that no two edges touch a common
vertex.)

First, what is the best known algorithm for computing a maximum weight
matching in a non-bipartite graph.  Here, best is with respect to
worst-case asymptotic time.

Second, which matching algorithm is the best to implement on sparse
graphs of around 1000 vertices.  Here, best does not necessarily mean
simplest to program, but rather, fast in practise.

Third, what is the best known algorithm for generating matchings in
decreasing order of weight for a non-bipartite graph.  Here, worst-case
asymptotic time is of interest.

And fourth, what is the matchings generator to implement.

Thanks in advance for any references to journal papers or conference
proceedings.
---
John Kececioglu

Department of Computer Science, University of Arizona, Tucson, Arizona 85721
"Through small apertures we glimpse abysses whose somber depths turn us faint."
--
John Kececioglu

Department of Computer Science, University of Arizona, Tucson, Arizona 85721
"Through small apertures we glimpse abysses whose somber depths turn us faint."

Maximum Weight Matchings in Non-Bipartite Graphs

> I have four questions concerning algorithms for maximum weight
> matchings in non-bipartite graphs.  (A matching is a selection of
> edges from an undirected graph such that no two edges touch a common
> vertex.)

> First, what is the best known algorithm for computing a maximum weight
> matching in a non-bipartite graph.  Here, best is with respect to
> worst-case asymptotic time.

I don't know about best for this problem, but I have been working
on fast algorithms for the problem on sparse bipartitie graphs and the
answers may be of some help.

Assume you have nodes 1..i..n, edges 1..j..m, weight vector w,
and a matrix C of connections such that C\sub{ij} = 1 if edge j
touches node i, zero otherwise.  The the problem can be stated as:

maximize \sum{i=1,n}{w\sub{i} x\sub{i}}
subject to \sum{i=1,n}{C\sub{ij} x\sub{i} \le 1       all j
x\sub{i} \ge 0                             all i

This problem could be solved as a normal linear programming
problem, but it is usually much faster to solve a related problem.
Because it is much faster, you should probably solve the dual, then
use the Kuhn-Tucker conditions to recover x\sub{i}.  The dual is:

minimize \sum{j=1,m}{u\sub{j}}
subject to \sum{j=1,m}{C\sub{ij}u\sub{j}} \ge w\sub{i} all i
u\sub{j} \ge 0                              all j

In the bipartite case, I can transform the problem into an
Assignment Problem, then solve it by a variation of the Hungarian
Algorithm, but I don't see offhand how to do that here.  This problem
has the intuitive feel of being larger but simpler than the bipartitie
case, so you may want to do what I have done and develop a special
algorithm tailored to the problem.

> Second, which matching algorithm is the best to implement on sparse
> graphs of around 1000 vertices.  Here, best does not necessarily mean
> simplest to program, but rather, fast in practise.

A one thousand node problem takes about a second on a Sun-3, for
sparse matrices.  But I'm solving a different problem.  Solving the
dual above shouldn't take too long, and I think that you will have no
trouble recovering the primal variables, but it may take some work
(for my case a maximal flow problem) in this case it looks like
finding a solution among the edges for which C\sub{i,j} u\sub{j} = 0
for both end points.

With sparse matrix techniques minutes should be easy, seconds
possible.  I'm dealing with sparse matrices (and as I say a somewhat
different problem).

> Third, what is the best known algorithm for generating matchings in
> decreasing order of weight for a non-bipartite graph.  Here, worst-case
> asymptotic time is of interest.

Huh?  I can't answer this question without knowing whether you
want all solutions or just the first k.  If the later, think about the convex
polytope corresponding to the feasible region of the primal problem.
Finding the other good solutions by pivoting will find keep finding
new "good" solutions and will allow you to generate a bound on the
best solution not yet seen.  When you have more than k better than the
best not seen, sort them and take the best k.

If you need all solutions, this technique will find them, but
realize that that is a VERY big (exponential growth) number.

--

Robert I. Eachus

with STANDARD_DISCLAIMER;
use  STANDARD_DISCLAIMER;
function MESSAGE (TEXT: in CLEVER_IDEAS) return BETTER_IDEAS is...

I am looking for an implementation of the Maximum Weighted Matching algorithm
for non-bipartite graphs. This algorithm is described in

* J. Edmonds, Matching and a polyhedron with 0-1 vertices, J. Res. Nat. Bur.
Standards Sect.B, 69 (1965)
and in
* E. Lawler, Combinatorial Optimization, Networks and Matroids, Holt, Rinehart
and Winston, pp 251-252.

If you have an implementation (preferably ftp-able) please reply by e-mail. I
would also like to know of any references to this algo. which describe it
*completely*. The references I have cited leave out a lot of important details.

Thanking you in anticipation,

--
Samik Gupta

Eugene, OR 97403.
503-686-4140.