Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-23T19:43:30.408Z Has data issue: false hasContentIssue false
  • English
  • Français

Perfect Matching in General vs. Cubic Graphs:A Note on the Planar and Bipartite Cases

Published online by Cambridge University Press:  15 April 2002

E. Bampis ,
A. Giannakos ,
A. Karzanov ,
Y. Manoussakis  and
I. Milis
E. Bampis
Affiliation:
LaMI, Université d'Evry, boulevard des Coquibus, 91025 Evry Cedex, France; ([email protected])
A. Giannakos
Affiliation:
La.R.I.A., Université de Picardie-Jules Verne, 5 rue du Moulin Neuf, 80000 Amiens, France; ([email protected])
A. Karzanov
Affiliation:
Institute for System Analysis, 9, Prosp. 60 Let Octyabrya, 117312 Moscow, Russia.
Y. Manoussakis
Affiliation:
LRI, bâtiment 490, Université Paris-Sud, 91405 Orsay Cedex, France; ([email protected])
I. Milis
Affiliation:
Athens University of Economics and Business, Department of Informatics, 76 Patission St., 10434 Athens, Greece; ([email protected])
Get access

Abstract

It is known that finding a perfect matching in a general graph is AC0-equivalent to finding a perfect matching in a 3-regular (i.e. cubic) graph. In this paper we extend this result to both, planar and bipartite cases. In particular we prove that the construction problem for perfect matchings in planar graphs is as difficult as in the case of planar cubic graphs like it is known to be the case for the famous Map Four-Coloring problem. Moreover we prove that the existence and construction problems for perfect matchings in bipartite graphs are as difficult as the existence and construction problems for a weighted perfect matching of O(m) weight in a cubic bipartite graph.

Keywords

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 34 , Issue 2 , March 2000 , pp. 87 - 97
Copyright
© EDP Sciences, 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alt, H., Blum, N., Mehlhron, K. and Paul, M., Computing a maximum cardinality matching in a bipartite graph in time $O(n^{1.5}\sqrt{m / \log n}$ ). Inform. Process. Lett. 37 (1991) 237-240. CrossRef
E. Bampis, A. Giannakos, A. Karzanov, I. Milis and Y. Manoussakis, Matchings in cubic graphs are as difficult as in general graphs, Rapport de Recherche No. 12. LaMI, Université d' Evry - Val d'Essonne (1995).
Cole, R. and Vishkin, U., Approximate and exact parallel scheduling, Part 1: The basic technique with applications to optimal parallel list ranking in logarithmic time. SIAM J. Comput. 17 (1988) 128-142. CrossRef
Chiba, N., Nishizeki, T. and Saito, N., Applications of the planar separator theorem. J. Inform. Process. 4 (1981) 203-207.
Dahlhaus, E. and Karpinski, M., Perfect matching for regular graphs is AC 0-hard for the general matching problem. J. Comput. System Sci. 44 (1992) 94-102. CrossRef
Edmonds, J., Paths, trees and flowers. Canad. J. Math. 17 (1965) 449-467. CrossRef
T. Feder and R. Motwani, Clique partitions, graph compression and speeding-up algorithms, $23^{\rm th}$ STOC (1991) 123-133.
Goldberg, A., Plotkin, S. and Vaidya, M., Sublinear time parallel algorithms for matchings and related problems. J. Algorithms 14 (1993) 180-213. CrossRef
Greenlaw, R. and Petreschi, R., Cubic graphs. ACM Computing Surveys 27 (1995) 471-495. CrossRef
D.Yu. Grigoriev and M. Karpinski, The matching problem for bipartite graphs with polynomially bounded permanents is in NC, $28^{\rm th}$ FOCS (1987) 166-172.
Hagerup, T., Optimal parallel algorithms on planar graphs. Inform. and Comput. 84 (1990) 71-96. CrossRef
M. Karpinski and W. Rytter, Fast parallel algorithms for graph matching problems. Oxford University Press, preprint (to appear).
G. Lev, N. Pippenger and L. Valiant, A fast parallel algorithm for routing in permutation networks. IEEE Trans. Comput. C-30 (1981) 93-100.
Liang, Y.D., Finding a maximum matching in a circular-arc graph. Inform. Process. Lett. 35 (1993) 185-193. CrossRef
L. Lovasz and M. Plummer, Matching Theory. Elsevier Science Publishers (1986).
S. Micali and V.V. Vazirani, An $O(\vert V\vert^{\frac {1}{2}}\vert E\vert)$ algorithm for finding maximum matchings in general graphs, $21^{\rm th}$ FOCS (1980) 17-23.
G.L. Miller and J. Naor, Flow in planar graphs with multiply sources and sinks, Proc. $30^{\rm th}$ FOCS (1989) 112-117.
A. Moitra and R. Jonhson, Parallel algorithms for maximum matching and other problems in interval graphs, TR 88-927. Cornell University (1988).
Mulmuley, K., Vazirani, U.V. and Vazirani, V.V., Matching is as easy as matrix inversion. Combinatorica 7 (1987) 105-113. CrossRef
T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms. North-Holland (1988).
O. Ore, The four color problem. Academic Press, New York (1967).
Plummer, M.D., Matching and vertex packing: how ``hard" are they?, Quo Vadis, Graph Theory?, edited by J. Gimbel, J.W. Kennedy and L.V. Quintas. Ann. Discrete Math. 55 (1993) 275-312. CrossRef
S.V. Ramachandran and J.H. Reif, An optimal parallel algorithm for graph planarity, $30^{\rm th}$ FOCS (1989) 282-287.
Rabin, M.O., Maximum matching in general graphs through randomization. J. Algorithms 10 (1989) 557-567. CrossRef
Vazirani, V.V., NC algorithms for computing the number of perfect matchings in K 3,3-free graphs and related problems. Inform. and Comput. 80 (1989) 152-164. CrossRef
Vazirani, V.V., A theory of alternating paths and blossoms for proving correctness of the $O(\sqrt{V}E)$ general graph maximum matching algorithm. Combinatorica 14 (1994) 71-109. CrossRef