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

E. Bampis; A. Giannakos; A. Karzanov; Y. Manoussakis; I. Milis

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 34, Issue: 2, page 87-97
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBampis, E., et al. "Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases." RAIRO - Theoretical Informatics and Applications 34.2 (2010): 87-97. <http://eudml.org/doc/222060>.

@article{Bampis2010,

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.
},

author = {Bampis, E., Giannakos, A., Karzanov, A., Manoussakis, Y., Milis, I.},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {perfect matching; planar graphs; cubic graphs},

language = {eng},

month = {3},

number = {2},

pages = {87-97},

publisher = {EDP Sciences},

title = {Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases},

url = {http://eudml.org/doc/222060},

volume = {34},

year = {2010},

}

TY - JOUR

AU - Bampis, E.

AU - Giannakos, A.

AU - Karzanov, A.

AU - Manoussakis, Y.

AU - Milis, I.

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

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 34

IS - 2

SP - 87

EP - 97

AB -
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.

LA - eng

KW - perfect matching; planar graphs; cubic graphs

UR - http://eudml.org/doc/222060

ER -

## References

top- H. Alt, N. Blum, K. Mehlhron and M. Paul, Computing a maximum cardinality matching in a bipartite graph in time $O({n}^{1.5}\sqrt{m/logn}$ ). Inform. Process. Lett.37 (1991) 237-240. Zbl0714.68036
- 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). Zbl0959.05092
- R. Cole and U. Vishkin, 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. Zbl0637.68038
- N. Chiba, T. Nishizeki and N. Saito, Applications of the planar separator theorem. J. Inform. Process.4 (1981) 203-207. Zbl0477.68069
- E. Dahlhaus and M. Karpinski, Perfect matching for regular graphs is AC0-hard for the general matching problem. J. Comput. System Sci.44 (1992) 94-102. Zbl0743.68072
- J. Edmonds, Paths, trees and flowers. Canad. J. Math.17 (1965) 449-467. Zbl0132.20903
- T. Feder and R. Motwani, Clique partitions, graph compression and speeding-up algorithms, ${23}^{\mathrm{th}}$ STOC (1991) 123-133. Zbl0831.68073
- A. Goldberg, S. Plotkin and M. Vaidya, Sublinear time parallel algorithms for matchings and related problems. J. Algorithms14 (1993) 180-213. Zbl0769.68034
- R. Greenlaw and R. Petreschi, Cubic graphs. ACM Computing Surveys27 (1995) 471-495.
- D.Yu. Grigoriev and M. Karpinski, The matching problem for bipartite graphs with polynomially bounded permanents is in NC, ${28}^{\mathrm{th}}$ FOCS (1987) 166-172.
- T. Hagerup, Optimal parallel algorithms on planar graphs. Inform. and Comput.84 (1990) 71-96. Zbl0689.68056
- M. Karpinski and W. Rytter, Fast parallel algorithms for graph matching problems. Oxford University Press, preprint (to appear). Zbl0895.05050
- G. Lev, N. Pippenger and L. Valiant, A fast parallel algorithm for routing in permutation networks. IEEE Trans. Comput.C-30 (1981) 93-100. Zbl0455.94047
- Y.D. Liang, Finding a maximum matching in a circular-arc graph. Inform. Process. Lett.35 (1993) 185-193. Zbl0768.68159
- L. Lovasz and M. Plummer, Matching Theory. Elsevier Science Publishers (1986).
- S. Micali and V.V. Vazirani, An $O\left(\right|V{|}^{\frac{1}{2}}\left|E\right|)$ algorithm for finding maximum matchings in general graphs, ${21}^{\mathrm{th}}$ FOCS (1980) 17-23.
- G.L. Miller and J. Naor, Flow in planar graphs with multiply sources and sinks, Proc. ${30}^{\mathrm{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).
- K. Mulmuley, U.V. Vazirani and V.V. Vazirani, Matching is as easy as matrix inversion. Combinatorica7 (1987) 105-113. Zbl0632.68041
- T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms. North-Holland (1988). Zbl0647.05001
- O. Ore, The four color problem. Academic Press, New York (1967). Zbl0149.21101
- M.D. Plummer, 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. Zbl0801.68066
- S.V. Ramachandran and J.H. Reif, An optimal parallel algorithm for graph planarity, ${30}^{\mathrm{th}}$ FOCS (1989) 282-287.
- M.O. Rabin, Maximum matching in general graphs through randomization. J. Algorithms10 (1989) 557-567. Zbl0689.68092
- V.V. Vazirani, NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems. Inform. and Comput.80 (1989) 152-164. Zbl0673.05075
- V.V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the $O\left(\sqrt{V}E\right)$ general graph maximum matching algorithm. Combinatorica14 (1994) 71-109. Zbl0806.05058

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.