Almost-optimum speed-ups of algorithms for bipartite matching and related problems

ABSTRACT

We present algorithms for matching and related problems that run on an EREW PRAM with p processors. Given is a bipartite graph G with n vertices, m edges, and integral edge costs at most N in magnitude. We give an algorithm for the assignment problem (minimum cost perfect bipartite matching) that runs in &Ogr;(√nm log (nN)(log(2p))/p) time and &Ogr;(m) space, for p ≤ m/(√nlog2n). For p = 1 this improves the best known sequential algorithm, and is within a factor of log (nN) of the best known bound for the problem without costs (maximum cardinality matching). For p > 1 the time is within a factor of log p of optimum speed-up. Extensions include an algorithm for maximum cardinality bipartite matching with slightly better processor bounds, and similar results for bipartite degree-constrained subgraph problems (with and without costs). Our ideas also extend to general graph matching problems.

REFERENCES

• B: R.F', Ilrcnt, "'l'he parallel ~.vahJal.lo,, of goncral aril.htlwtic esprcssiolm", J. AC'M ,~1, 2, 197,'t, pp. 2(11-206.
• C: R. Cole, "l'arallel merge sort", Proc. 27th Annual Syrup. on Found. of Comp. Sci,, 1986, pp. 511-516.
• Dan: G,B. Dantzig, Linear Programming and Eztensioas, Princeton Univ. Press, Princeton, N.J., 1963.
• Dij: E. Dijkstra, "A note on two problelns ill connexion with graphs", Numerisehe Mathematik 1, pp. 269-271, 1959.
• Din: E.A. Dinie, "Algorithm for solution of a problem of maximum flow in a network with power estimation", Soy. Math. Dokl. Ii, 5, 1970, pp. 1277-1280.
• ET: S. Even and R.E. Tarjan, "Network flow and testing graph com~ectivity", $IA,tl J. Uomput. 4', 4, 1975, pp. 507-518.
• FM: D. Fernandez-B~caand C.U. Xlartel, "Theoretical efficiency of maximuni Ilow algorithms on networks witl~ small integer capacities", .,1 !go~tbmica, t.o a pln,ar~
• FT: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• G85: Harold N. Gabow, Scaling algorithms for network problems, Journal of Computer and System Sciences, v.31 n.2, p.148-168, Sept. 1985 [doi>10.1016/0022-0000(85)90039-X]
• G87: H.N. Gabow, "Duality and parallcl algorithms for graph matching", manuscript.
• GaT87: II.N. Gabow and R.E. Tarjaa, "Faster scaling Mgorithn~ for network problems", manuscript.
• GaT88a: H.N. Gabow and R.E. Tarjan, "Improved parallel and sequential algorithms for network flow problems", manuscript.
• GaT88b: II.N. Gabow and R.E. Tarjaa, "Faster scaling algorithms for generM graph matching problems", manuscript.
• GoT: A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States [doi>10.1145/28395.28397]
• GP: Z. G;dil and V. Pan, "lnlprowM processor Imlltlds for ttltz, cbraic :ttul cottd~ituttorial IJrolJh'lllS in RN(:", t'rbc. 26ta A,nual Syrup. on 1%undalions of ('omp. 5'ci., 1985, pp. 490-,195.
• GSS: L.M. Goldschlager, R.A. S!taw and J. Staples, "The maximum flow problem is logspace complete for P, Theoretical Comp. S'ci. ,91, 1982, pp. 105-Iii.
• GW: Harold Gabow , Herbert Westermann, Forests, frames, and games: algorithms for matroid sums and applications, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.407-421, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62252]
• HK: J. Ilopcroft and R. Karp, "An n5/~ algorithm for maximum matchings in bipartite graphs", SIAM J. Comp. 2, 4, 1973, pp. 225-231.
• KUW: R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Combinatorica, v.6 n.1, p.35-48, 1986 [doi>10.1007/BF02579407]
• MVV: K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
• KC: Taenam Kim , Kyung-Yong Chwa, An O(n log n log log n) parallel maximum matching algorithm for bipartite graphs, Information Processing Letters, v.24 n.1, p.15-17, January 1987 [doi>10.1016/0020-0190(87)90193-1]
• L: E.L. Lawler, Combinatorial Optimization: Networks and Matroids, IIolt, Rinehart and Winston, New York, 1976.
• SV: Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
• T: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory