R. Motwani
ABSTRACT
Hall's Theorem states that a bipartite graph has a perfect matching if and only if every set of vertices has an equal number of neighbours. Equivalently, it states that every non-maximum matching has an augmenting path if the graph is an expander with expansion 1. We use this insight to demonstrate that if a graph is an expander with expansion more than one than every non-maximum matching has a short augmenting path and, therefore, the bipartite matching algorithm performs much better on such graphs than in the worst case. We then apply this idea to the average case analysis of various augmenting path algorithms and to the approximation of the permanent. In particular, we demonstrate that the following algorithms perform much better on the average than in the worst case. In fact, they will rarely exhibit their worst-case running times.
Hopcroft-Karp's algorithm for bipartite matchings.
Micali-Vazirani's and Even-Kariv's algorithms for non-bipartite matchings.
Gabow-Tarjan's parallel algorithm for bipartite matchings.
Dinic's algorithm for k-factors and 0-1 network flows.
Jerrum-Sinclair's approximation scheme for the permanent.
It seems rather surprising that the algorithms which are the fastest known for worst-case inputs also do exceedingly on almost every graph.
- 1.D. Angluin and L. Valiant, "l:ast probabilistic algorithms for Hamiltonian circuits and matchings," Journal of Computer and System Sciences, vol. 19, pp. 155-193, 1979.Google Scholar
- 2.B. Bollob~, Random Graphs, Academic Press, 1985.Google Scholar
- 3.B. Bollobas and A. M. Frieze, "On Matchings and Hamiltonian Circuits in Random Graphs," Annals of Discrete Mathematics, vol. 28, pp. 23-46, 1985.Google Scholar
- 4.B. Bollobas, T. I. Fenner, and A. M. Frieze, "An Algorithm for finding Hamilton Cycles in a Random Graph," Proceedings of the 17th ACM Symposium on Theory of Computing, pp. 430-439, 1985. Google ScholarDigital Library
- 5.A.Z. Broder, "How hard is it to marry at random? (On the approximation of the permanent)," Proceedings of the 18th ACM Symposium on Theory of Computing, pp. 50-58, t986. Google ScholarDigital Library
- 6.U. Derigs and A. Heske, "A Computational Study on Some Methods for Solving the Cardinality Matching Problem," Report 79/2!, Mathematisches Institut der Universit~t zu Kbln, 1979.Google Scholar
- 7.E.A. Dinic, "Algorithm for solution of a problem of maximum flow in networks with power estimation,'' Soviet Math. Doklady, vol. 11, pp. 1277- 1280, 1970.Google Scholar
- 8.P. Erd6s and A. R6nyi, "On random graphs," Publ. Math. Debrecen, vol. 6, pp. 290-297, 1959.Google Scholar
- 9.P. Erd6s and A. R6nyi, "On random matrices," l~ubl. Math. Inst. Hungarian Academy of Sciences, vol. 8, pp. 455-461, 1964.Google Scholar
- 10.P. ErdlSs and A. R6nyi, "On the existence of a factor of degree one of a connected random graph," Acta Math. Acad. Sci. Hungar., vol. 17, pp. 359- 368, 1966.Google ScholarCross Ref
- 11.P. Erdbs and A. R6nyi, "On random matrices 1I," Studia Sci. Math. Hungar., vol. 3, pp. 459-464, 1968.Google Scholar
- 12.S. Even and O. Kariv, "An O(nZS)-Algorithm for Maximum Matching in General Graphs," Proc. 16th FOCS, pp. 100-112, 1975.Google Scholar
- 13.T.I. Fenner and A. M. Frieze, "On the Existence of Hamiltonian Cycles in a Class of Random Graphs," Discrete Mathematics, vol. 45, pp. 301- 305, 1983.Google ScholarDigital Library
- 14.A.M. Frieze, "Limit Distribution for the Existence of Hamiltonian Cycles in Random Bipartite Graphs," European Journal on Combinatorics, vol. 6, pp. 327-334, 1985.Google ScholarCross Ref
- 15.H. Gabow and R. Tarjan, "Almost Optimum Speed-ups of Algorithms for Bipartite Matching and Related Problems," Proceedings of the 20th ACM Symposium on Theory of Computing, pp. 514-527, 1988. Google ScholarDigital Library
- 16.O. Goldschmidt and D. S. Hochbaum, "A fast perfeet matching algorithm in random graphs," Preprint, 1988.Google Scholar
- 17.P. Hall, "On representatives of subsets," Journal of London Mathematics Society, vol. I0, pp. 26-30, 1935.Google Scholar
- 18.H. Hamacher, "Numerical Investigations on the Maximal Flow Algorithm of Karzanov," Report 78-7, Mathematisches Institut der UniversitIR zu KtSln, 1978.Google Scholar
- 19.R. Hassin and E. Zemel, "Probabilistic analysis of the capacitatecl transportation problem," Discussion Paper No. 660, Center for Mathematical Studies in Economics and Management Science, Evanston, Illinois, 1985.Google Scholar
- 20.J.E. Hopcroft and R. M. Karp, "An O(nsa) algorithm for maximum matchings in bipartite graphs," SIAM Journal on Computing, vol. 2, pp. 225-231, 1973.Google ScholarCross Ref
- 21.M. Jerrum and A. Sinclair, "Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved," Proceedings of the 20th ACM Symposium on Theory of Computing, 1988. Google ScholarDigital Library
- 22.R.M. Karp and M. Sipser, "Maximum matchings in sparse random graphs," Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science, pp. 364-375, 1981.Google Scholar
- 23.R.M. Karp, J. K. Lenstra, C. J. H. McDiarmid, and A. H. G. Rinnooy Karl, "Probabilisfic Analysis," Combinatorial Optimization: Annotated Bibliographies (ed. M. O'hEigem~gh, J. K. Lenstra and A. H. G. Rinnooy Karl), pp. 52-88, John Wiley & Sons, 1985.Google Scholar
- 24.R.M. Karp and A. H. G. Rinnooy Karl, personal communication, 1986.Google Scholar
- 25.R.M. Karp, R. Motwani, and N. Nisan, "Probabilisfic Analysis of Network Flow Algorithms," submitted for publication to Mathematics of Operations Research, 1987. Google ScholarDigital Library
- 26.J. Koml6s and E. Szemer6di, "Limit Distribution for the Existence of Hamiltonian Cycles in a Random Graph," Discrete Mathematics, vol. 43, pp. 55-63, 1983.Google ScholarDigital Library
- 27.A.D. Korshunov, "A new version of the solution of a problem of Erd~Ss and R6nyi on Hamilton cycles," Annals of Discrete Mathematics, vol. 28, pp. 171-180, 1985.Google Scholar
- 28.S. Micali and V. Vazirani, "An O(IV}~-S. lEI) Algorithm for Finding Maximum Matchings in General Graphs," Proceedings of the 21st IEEE Symposium on Foundations of Computer Science, pp. 17-27, 1980.Google Scholar
- 29.R. Motwani, "Probabilistic Analysis of Matching and Network Flow Algorithms," Ph.D. Thesis, University of California at Berkeley, 1988. Google ScholarDigital Library
- 30.L. P6sa, "Hamiltonian Circuits in Random Graphs," Discrete Mathematics, vol. 14, pp. 359- 364, 1976.Google ScholarDigital Library
- 31.I, Pohl, "Improvements to the Dinic-Karzanov Network Flow Algorithm," Technical Report No. tiP. 77-11-001, Information Sciences, University of California at Santa Cruz, 1977.Google Scholar
- 32.L.G. Valiant, "The complexity of computing the permanent," Theoretical Computer Science, vol. 8, pp. 189-201, 1979.Google ScholarCross Ref
- 33.D.W. Walkup, "Matchings in random regular bipartite graphs," Discrete Mathematics, vol. 31, pp. 59-64, 1980.Google ScholarDigital Library
Index Terms
- Expanding graphs and the average-case analysis of algorithms for matchings and related problems
Recommendations
Induced matchings in asteroidal triple-free graphs
Special issue on stability in graphs and related topicsAn induced matching M of a graph G is a set of pairwise nonadjacent edges such that no two edges of M are joined by an edge in G. The problem of finding a maximum induced matching is known to be NP-hard even for bipartite graphs of maximum degree four. ...
Matchings in 3-vertex-critical graphs: The odd case
A subset of vertices D of a graph G is a dominating set for G if every vertex of G not in D is adjacent to one in D. The cardinality of any smallest dominating set in G is denoted by @c(G) and called the domination number of G. Graph G is said to be @c-...
Rainbow matchings in strongly edge-colored graphs
A rainbow matching of an edge-colored graph G is a matching in which no two edges have the same color. There have been several studies regarding the maximum size of a rainbow matching in a properly edge-colored graph G in terms of its minimum degree ( G ...
Comments