Maximum matching in graphs with an excluded minor

ABSTRACT

We present a new randomized algorithm for finding a maximum matching in H-minor free graphs. For every fixed H, our algorithm runs in O(n^3ω/(ω+3)) < O(n^1.326) time, where n is the number of vertices of the input graph and ω < 2.376 is the exponent of matrix multiplication. This improves upon the previous O(n^1.5) time bound obtained by applying the O(mn^1/2)-time algorithm of Micali and Vazirani on this important class of graphs.

For graphs with bounded genus, which are special cases of H-minor free graphs, we present a randomized algorithm for finding a maximum matching in O(n^ω/2) < O(n^1.19) time. This extends a previous randomized algorithm of Mucha and Sankowski, having the same running time, that finds a maximum matching in a planar graphs.

We also present a deterministic algorithm with a running time of O(n^1+ω/2) < O(n^2.19) for counting the number of perfect matchings in graphs with bounded genus. This algorithm combines the techniques used by the algorithms above with the counting technique of Kasteleyn. Using this algorithm we can also count, within the same running time, the number of T-joins in planar graphs. As special cases, we get algorithms for counting Eulerian subgraphs (T = &phis;) and odd subgraphs (T = V) of planar graphs.

REFERENCES

• 1: {AST90} N. Alon, P. D. Seymour, and R. Thomas. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society, 3(4):801--808, 1990.
• 2: Norbert Blum, A New Approach to Maximum Matching in General Graphs, Proceedings of the 17th International Colloquium on Automata, Languages and Programming, p.586-597, July 16-20, 1990
• 3: {BM04} J. M. Boyer and W. J. Myrvold. On the cutting edge: Simplified O(n) planarity by edge addition. Journal of Graph Algorithms and Applications, 8(2):241--273, 2004.
• 4: Norishige Chiba , Takao Nishizeki , Shigenobu Abe , Takao Ozawa, A linear algorithm for embedding planar graphs using PQ-trees, Journal of Computer and System Sciences, v.30 n.1, p.54-76, Feb. 1985 [doi>10.1016/0022-0000(85)90004-2]
• 5: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 6: {Edm65} J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449--467, 1965.
• 7: {Geo73} A. George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10:345--363, 1973.
• 8: John R. Gilbert , Joan P. Hutchinson , Robert Endre Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithms, v.5 n.3, p.391-407, Sept. 1984 [doi>10.1016/0196-6774(84)90019-1]
• 9: {GL99a} A. Galluccio and M. Loebl. On the theory of Pfaffian orientations. I. Perfect matchings and permanents. Electron. J. Combin., 6:R6, 18 pp. (electronic), 1999.
• 10: {GL99b} A. Galluccio and M. Loebl. On the theory of Pfaffian orientations. II. T-joins, k-cuts, and duality of enumeration. Electronic Journal of Combinatorics, 6:R7, 10 pp. (electronic), 1999.
• 11: J. R. Gilbert , R. E. Tarjan, The analysis of a nested dissection algorithm, Numerische Mathematik, v.50 n.4, p.377-404, FEB. 1987 [doi>10.1007/BF01396660]
• 12: Harold N. Gabow , Robert E. Tarjan, Faster scaling algorithms for general graph matching problems, Journal of the ACM (JACM), v.38 n.4, p.815-853, Oct. 1991 [doi>10.1145/115234.115366]
• 13: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 14: {Jer03} M. Jerrum. Counting, sampling and integrating: Algorithms and complexity. Birkhäuser, 2003.
• 15: {Kas67} P. W. Kasteleyn. Graph theory and crystal physics. In Graph Theory and Theoretical Physics, pages 43--110. Academic Press, London, 1967.
• 16: {Kur30} C. Kuratowski. Sur le problèms des courbes gauches en topologie. Fundamenta Mathematicae, 15:271--283, 1930.
• 17: {Lit74} C. H. C. Little. An extension of Kasteleyn's method of enumerating the 1-factors of planar graphs. In Combinatorial mathematics (Proc. Second Australian Conf., Univ. Melbourne, Melbourne, 1973), pages 63--72. Lecture Notes in Math., Vol. 403. Springer, Berlin, 1974.
• 18: {Lov79} L. Lovász. On determinants, matchings, and random algorithms. In Fundamentals of computation theory, volume 2 of Math. Res., pages 565--574. Akademie-Verlag, Berlin, 1979.
• 19: {Lov06} L. Lovász. Graph minor theory. Bull. Amer. Math. Soc. (N.S.), 43(1):75--86 (electronic), 2006.
• 20: {LP86} L. Lovász and M. D. Plummer. Matching theory. North-Holland Publishing Co., Amsterdam, 1986. Annals of Discrete Mathematics, 29.
• 21: {LRT79} R. J. Lipton, D. J. Rose, and R. E. Tarjan. Generalized nested dissection. SIAM Journal on Numerical Analysis, 16(2):346--358, 1979.
• 22: {LT79} R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177--189, 1979.
• 23: {McC04} W. McCuaig. Pólya's permanent problem. Electronic Journal of Combinatorics, 11(1):Research Paper 79, 83 pp. (electronic), 2004.
• 24: Bojan Mohar, A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface, SIAM Journal on Discrete Mathematics, v.12 n.1, p.6-26, Jan. 1999 [doi>10.1137/S089548019529248X]
• 25: {MS04a} M. Mucha and P. Sankowski. Maximum matchings in planar graphs via gaussian elimination. In Proc. of 12th ESA, pages 532--543, 2004.
• 26: 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]
• 27: {MV80} S. Micali and V. V. Vazirani. An O(√|V| · |E|) algorithm for finding maximum matching in general graphs. In Proc. of 21st FOCS, pages 17--27, 1980.
• 28: N. Robertson , P. D. Seymour, Graph minors. VIII. A Kuratowski theorem for general surfaces, Journal of Combinatorial Theory Series B, v.48 n.2, p.255-288, Apr. 1990 [doi>10.1016/0095-8956(90)90121-F]
• 29: Neil Robertson , P. D. Seymour, Graph Minors. XX. Wagner's conjecture, Journal of Combinatorial Theory Series B, v.92 n.2, p.325-357, November 2004 [doi>10.1016/j.jctb.2004.08.001]
• 30: {RST99} N. Robertson, P. D. Seymour, and R. Thomas. Permanents, Pfaffian orientations, and even directed circuits. Annals of Mathematics. Second Series, 150(3):929--975, 1999.
• 31: {RW05} B. Reed and D. R. Wood. Fast separation in a graph with an excluded minor. In Proc. of the 2005 European Conference on Combinatorics, Graph Theory and Applications (EURO-COMB), DMTCS proc. AE, pages 45--50, 2005.
• 32: {Tho81} C. Thomassen. Kuratowski's theorem. Journal of Graph Theory, 5:225--241, 1981.
• 33: {Val79} L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189--201, 1979.
• 34: Vijay V. Vazirani, NC algorithms for computing the number of perfect matchings in K_3,3-free graph and related problems, Information and Computation, v.80 n.2, p.152-164, Feb. 1989 [doi>10.1016/0890-5401(89)90017-5]
• 35: {Vaz94} V. V. Vazirani. A theory of alternating paths and blossoms for proving correctness of the O( √V E) general graph maximum matching algorithm. Combinatorica, 14(1):71--109, 1994.
• 36: {Wag37} K. Wagner. Über eine Eigenschaft der ebenen Komplexe. Mathematische Annalen, 114(1):570--590, 1937.
• 37: David Bruce Wilson, Determinant algorithms for random planar structures, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.258-267, January 05-07, 1997, New Orleans, Louisiana, United States