Perfect matchings via uniform sampling in regular bipartite graphs

ABSTRACT

In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time O(mn), dates back to König's work in 1916 (here m = nd is the number of edges in the graph, 2n is the number of vertices, and d is the degree of each node). The currently most efficient algorithm takes time O(m), and is due to Cole, Ost, and Schirra. We improve this running time to O(min{m, n^2.5ln n/d}); this minimum can never be larger than O(n^1.75√ln n). We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a d-regular bipartite graph independently with a probability p = O(n ln n/d²) then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to non-existence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Karger's sampling theorem for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the O(m√n) algorithm (due to Hopcroft and Karp) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to poly-logarithmic factors (in fact, up to ln² n).

REFERENCES

• 1: Gagan Aggarwal , Rajeev Motwani , Devavrat Shah , An Zhu, Switch Scheduling via Randomized Edge Coloring, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.502, October 11-14, 2003
• 2: Andras A. Benczur , Michel X. Goemans, Cut structures and randomized algorithms in edge-connectivity problems, Massachusetts Institute of Technology, 1997
• 3: G. Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumán Rev. Ser. A, 5:147--151, 1946.
• 4: B. Bollobas. Modern graph theory. Springer, 1998.
• 5: R. Cole and J. E. Hopcroft. On edge coloring bipartite graphs. SIAM J. Comput., 11(3):540--546, 1982.
• 6: R. Cole, K. Ost, and S. Schirra. Edge-coloring bipartite multigraphs in O(E log D) time. Combinatorica, 21(1):5--12, 2001.
• 7: H. N. Gabow and O. Kariv. Algorithms for edge coloring bipartite graphs and multigraphs. SIAM J. Comput., 11(1):117--129, 1982.
• 8: J. E. Hopcroft and R. M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4):225--231, 1973.
• 9: David R. Karger, Random sampling in cut, flow, and network design problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.648-657, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195422]
• 10: David R. Karger, Using randomized sparsification to approximate minimum cuts, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.424-432, January 23-25, 1994, Arlington, Virginia, United States
• 11: D. König. Uber graphen und ihre anwendung auf determinententheorie und mengenlehre. Math. Annalen, 77:453465, 1916.
• 12: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 13: 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]
• 14: Daniel A. Spielman , Nikhil Srivastava, Graph sparsification by effective resistances, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374456]
• 15: Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007372]
• 16: J. von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the optimal assignment problem to the Theory of Games, 2:5--12, 1953.

INDEX TERMS

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