An O(VE) algorithm for ear decompositions of matching-covered graphs

ABSTRACT

Our main result is an O(nm)-time (deterministic) algorithm for constructing an ear decomposition of a matching-covered graph, where n and m denote the number of nodes and edges. The improvement in the running time comes from new structural results that give a sharpened version of Lovász and Plummer's Two-Ear Theorem. Our algorithm is based on O(nm)-time algorithms for two other fundamental problems in matching theory, namely, finding all the allowed edges of a graph, and finding the canonical partition of an elementary graph. To the best of our knowledge, no faster deterministic algorithms are known for these two fundamental problems.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Carvalho, M. H., Lucchesi, C. L., and Murty, U. S. R. 2002. (i) On a conjecture of Lovász concerning bricks I. The characteristic of a matching covered graph. J. Combin. Theor. B 85, 94--136; (ii) On a conjecture of Lovász concerning bricks II. Bricks of finite characteristic. J. Combin. Theor. B 85, 137--180.
• 3: Carvalho, M. H., Lucchesi, C. L., and Murty, U. S. R. 2003. The matching lattice, In Recent Advances in Algorithms and Combinatorics, B. Reed and C. L. Sales, Eds. CMS Books in Mathematics. Springer, Berlin, Germany, 1--26.
• 4: Joseph Cheriyan, Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory, SIAM Journal on Computing, v.26 n.6, p.1635-1655, Dec. 1997 [doi>10.1137/S0097539793256223]
• 5: Edmonds, J. 1965. Paths, trees and flowers. Can. J. Math. 17, 449--467.
• 6: Gabow, H. N., and Tarjan, R. E. 1985. A linear time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 209--221.
• 7: Andrew V. Goldberg , Alexander V. Karzanov, Maximum skew-symmetric flows and matchings, Mathematical Programming: Series A and B, v.100 n.3, p.537-568, July 2004 [doi>10.1007/s10107-004-0505-z]
• 8: Hetyei, G. 1964. Rectangular configurations which can be covered by 2 × 1 rectangles. Pésci Tan. Föisk. Közl. 8, 351--367.
• 9: Kotzig, A. 1959/1960. Ein beitrag zur theorie der endlichen graphen I--II--III. Mat. Fyz. Casopis 9, 73--91, 136--159; 10, 205--215.
• 10: Little, C. H. C., and Rendl, F. 1989. An algorithm for the ear decomposition of a 1-factor covered graph. J. Austral. Math. Soc. (Series A) 46, 296--301.
• 11: Lovász, L. 1983. Ear decompositions of matching-covered graphs. Combinatorica 3, 105--117.
• 12: László Lovász, Matching structure and the matching lattice, Journal of Combinatorial Theory Series B, v.43 n.2, p.187-222, Oct. 1987 [doi>10.1016/0095-8956(87)90021-9]
• 13: Lovász, L., and Plummer, M. D. 1975. On bicritical graphs. Colloq. Math. Soc. Jáinos Bolyai 10, 1051--1079.
• 14: Lovász, L., and Plummer, M. D. 1986. Matching Theory. Akadémiai Kiadó, Budapest, Hungary.
• 15: Micali, S., and Vazirani, V. V. 1980. An O(&surd;∣V∣∣E∣) algorithm for finding maximum matching in general graphs. In Proceedings of the 21st IEEE F.O.C.S. 17--27.
• 16: Murty, U. S. R. 1994. The matching lattice and related topics. Preliminary report. Dept. of Combinatorics & Optimization, University Waterloo, Waterloo, Ont., Canada.
• 17: Naddef, D., and Pulleyblank, W. R. 1982. Ear decompositions of elementary graphs and GF(2)-rank of perfect matchings. In Proceedings of the Bonn Workshop on Combinatorial Optimization, A. Bachem, M. Grötschel, and B. Korte, Eds. Ann. Discrete Math., 16, 241--260.
• 18: M. O. Rabin , V. V. Vazirani, Maximum matchings in general graphs through randomization, Journal of Algorithms, v.10 n.4, p.557-567, Dec. 1989 [doi>10.1016/0196-6774(89)90005-9]
• 19: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 20: Vazirani, V. V. 1994. A theory of alternating paths and blossoms for proving correctness of the O(&surd;VE) general graph matching algorithm. Combinatorica 14, 71--109.
• 21: Schrijver, A. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag, Berlin, Germany.
• 22: Zoltán Szigeti, The two ear theorem on matching-covered graphs, Journal of Combinatorial Theory Series B, v.74 n.1, p.104-109, Sept. 1998 [doi>10.1006/jctb.1998.1824 ]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

General Terms:
Algorithms, Theory

Keywords:
Matching theory, ear decompositions