Maximum Weight Matchings in Non-Bipartite Graphs

Maximum Weight Matchings in Non-Bipartite Graphs

Post by John Kececiog » Sun, 02 Dec 1990 21:14:00



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

Post by Robert I. Each » Sun, 02 Dec 1990 23:41:00



  > 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

     (I tried to trade off between TeX rigor and readability...)

     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...

 
 
 

1. Maximum Weight Matching for non-bipartite graphs

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.

2. preloading shared libraries

3. Graph Theory Question: non-bipartite weighted minimum cost matching algorithms

4. Combobox button

5. Maximum weight matchings in bipartite graphs

6. to repair span disks

7. maximum cost matching in Bipartite Graph

8. Need help in talking to a Lotus 123 spreadsheet from MFC App

9. Maximum weightd matching in bipartite graphs

10. Max weighted matching in bipartite graphs

11. Weighted bipartite graph matching.

12. Maximum cardinality bipartite matching

13. bipartite weighted perfect matching