Computing large matchings fast

ABSTRACT

In this paper we present algorithms for computing large matchings in 3-regular graphs, graphs with maximum degree 3, and 3-connected planar graphs. The algorithms give a guarantee on the size of the computed matching and take linear or slightly superlinear time. Thus they are faster than the best-known algorithm for computing maximum matchings in general graphs, which runs in O(√nm) time, where n denotes the number of vertices and m the number of edges of the given graph. For the classes of 3-regular graphs and graphs with maximum degree 3 the bounds we achieve are known to be best possible.

We also investigate graphs with block trees of bounded degree, where the d-block tree is the adjacency graph of the d-connected components of the given graph. In 3-regular graphs and 3-connected planar graphs with bounded-degree 2- and 4-block trees, respectively, we show how to compute maximum matchings in slightly superlinear time.

REFERENCES

• 1: Algorithmic Solutions. The LEDA user manual version 5.2. www.algorithmic-solutions.info/leda_manual.
• 2: Jonathan Aronson , Alan Frieze , Boris G. Pittel, Maximum matchings in sparse random graphs: Karp-Sipser revisited, Random Structures & Algorithms, v.12 n.2, p.111-177, March 1998 [doi>10.1002/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#]
• 3: Therese Biedl, Linear reductions of maximum matching, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.825-826, January 07-09, 2001, Washington, D.C., United States
• 4: Therese C. Biedl , Prosenjit Bose , Erik D. Demaine , Anna Lubiw, Efficient algorithms for Petersen's matching theorem, Journal of Algorithms, v.38 n.1, p.110-134, Jan. 2001 [doi>10.1006/jagm.2000.1132]
• 5: T. Biedl, E. D. Demaine, C. A. Duncan, R. Fleischer, and S. G. Kobourov. Tight bounds on maximal and maximum matchings. Discrete Math., 285(1--3):7--15, 2004.
• 6: N. Chiba , T. Nishizeki, The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs, Journal of Algorithms, v.10 n.2, p.187-211, June 1989 [doi>10.1016/0196-6774(89)90012-6]
• 7: R. Cole, K. Ost, and S. Schirra. Edge-coloring bipartite multigraphs in O(E log D) time. Combinatorica, 21:5--12, 2001.
• 8: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 9: Harold N. Gabow, An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs, Journal of the ACM (JACM), v.23 n.2, p.221-234, April 1976 [doi>10.1145/321941.321942]
• 10: Harold N. Gabow , Haim Kaplan , Robert E. Tarjan, Unique maximum matching algorithms, Journal of Algorithms, v.40 n.2, p.159-183, August 2001 [doi>10.1006/jagm.2001.1167]
• 11: P. Hall. On representatives of subsets. Jour. London Math. Soc., 10:26--30, 1935.
• 12: Pierre Hansen , Maolin Zheng, A linear algorithm for perfect matching in hexagonal systems, Discrete Mathematics, v.122 n.1-3, p.179-196, Nov. 15, 1993 [doi>10.1016/0012-365X(93)90294-4]
• 13: Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM (JACM), v.48 n.4, p.723-760, July 2001 [doi>10.1145/502090.502095]
• 14: Arkady Kanevsky , Roberto Tamassia , Giuseppe Di Battista , Jianer Chen, On-line maintenance of the four-components of a graph (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.793-801, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185451]
• 15: G. Kant. A more compact visibility representation. Intern. J. Comput. Geom. Appl., 7(3):197--210, 1997.
• 16: Claire Kenyon , Eric Rémila, Perfect matchings in the triangular lattice, Discrete Mathematics, v.152 n.1-3, p.191-210, May 20, 1996 [doi>10.1016/0012-365X(94)00304-2]
• 17: L. Lovász and M. D. Plummer. Matching Theory. North Holland, Amsterdam, 1986.
• 18: S. Micali and V. V. Vazirani. An O(√|V| · |E|) algorithm for finding maximum matchings in general graphs. In Proc. 21st Annu. IEEE Sympos. Found. Comput. Sci. (FOCS'80), pages 17--27, 1980.
• 19: Marcin Mucha , Piotr Sankowski, Maximum Matchings via Gaussian Elimination, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.248-255, October 17-19, 2004 [doi>10.1109/FOCS.2004.40]
• 20: Marcin Mucha , Piotr Sankowski, Maximum matchings in planar graphs via gaussian elimination, Algorithmica, v.45 n.1, p.3-20, April 2006 [doi>10.1007/s00453-005-1187-5]
• 21: T. Nishizeki and I. Baybars. Lower bounds on the cardinality of the maximum matchings of planar graphs. Discrete Math., 28(3):255--267, 1979.
• 22: J. Petersen. Die Theorie der regulären Graphs. Acta Mathematics, 15:193--220, 1891.
• 23: Suneeta Ramaswami , Pedro Ramos , Godfried Toussaint, Converting triangulations to quadrangulations, Computational Geometry: Theory and Applications, v.9 n.4, p.257-276, March 1998 [doi>10.1016/S0925-7721(97)00019-9]
• 24: I. Rutter and A. Wolff. Computing large matchings fast. Technical Report 2007-19, Fakultät für Informatik, Universität Karlsruhe, 2007. Available at www.ubka.uni-karlsruhe.de/indexer-vvv/ira/2007/19.
• 25: Alexander Schrijver, Bipartite Edge Coloring in $O(\Delta m)$ Time, SIAM Journal on Computing, v.28 n.3, p.841-846, Feb. 1999 [doi>10.1137/S0097539796299266]
• 26: J. Siek, L.-Q. Lee, and A. Lumsdaine. The Boost Graph Library documentation. www.boost.org/libs/graph, visited 07/04/2007.
• 27: W.-B. Strothmann. Bounded Degree Spanning Trees. PhD thesis, Heinz-Nixdorf-Institut, Universität Pader-born, 1997.
• 28: R. E. Tarjan. Depth first search and linear graph algorithms. SIAM J. Comput., 2:146--160, 1972.
• 29: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 30: Robin Thomas , Xingxing Yu, 4-connected projective-planar graphs are Hamiltonian, Journal of Combinatorial Theory Series B, v.62 n.1, p.114-132, Sept. 1994 [doi>10.1006/jctb.1994.1058]
• 31: Mikkel Thorup, Near-optimal fully-dynamic graph connectivity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.343-350, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335345]
• 32: William P. Thurston, Conway's tiling groups, American Mathematical Monthly, v.97 n.8, p.757-756, Oct. 1990 [doi>10.2307/2324578]
• 33: W. T. Tutte. The factorization of linear graphs. J. Lond. Math. Soc., 22:107--111, 1947.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph labeling

General Terms:
Algorithms, Design, Theory