johnk@cs.arizona.edu (John Kececioglu) (12/09/89)
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 johnk@cs.arizona.edu or arizona!johnk.uucp Department of Computer Science, University of Arizona, Tucson, Arizona 85721 "Through small apertures we glimpse abysses whose somber depths turn us faint." -- John Kececioglu johnk@cs.arizona.edu or arizona!johnk.uucp Department of Computer Science, University of Arizona, Tucson, Arizona 85721 "Through small apertures we glimpse abysses whose somber depths turn us faint."
eachus@aries.mitre.org (Robert I. Eachus) (12/15/89)
In article <16017@megaron.cs.arizona.edu> johnk@cs.arizona.edu (John Kececioglu) writes: > 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...