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

Abstract

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

How to cite

top

Bampis, 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
  1. H. Alt, N. Blum, K. Mehlhron and M. Paul, Computing a maximum cardinality matching in a bipartite graph in time O ( n 1 . 5 m / log n ). Inform. Process. Lett.37 (1991) 237-240.  Zbl0714.68036
  2. 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
  3. 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
  4. N. Chiba, T. Nishizeki and N. Saito, Applications of the planar separator theorem. J. Inform. Process.4 (1981) 203-207.  Zbl0477.68069
  5. 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
  6. J. Edmonds, Paths, trees and flowers. Canad. J. Math.17 (1965) 449-467.  Zbl0132.20903
  7. T. Feder and R. Motwani, Clique partitions, graph compression and speeding-up algorithms, 23 th STOC (1991) 123-133.  Zbl0831.68073
  8. A. Goldberg, S. Plotkin and M. Vaidya, Sublinear time parallel algorithms for matchings and related problems. J. Algorithms14 (1993) 180-213.  Zbl0769.68034
  9. R. Greenlaw and R. Petreschi, Cubic graphs. ACM Computing Surveys27 (1995) 471-495.  
  10. D.Yu. Grigoriev and M. Karpinski, The matching problem for bipartite graphs with polynomially bounded permanents is in NC, 28 th FOCS (1987) 166-172.  
  11. T. Hagerup, Optimal parallel algorithms on planar graphs. Inform. and Comput.84 (1990) 71-96.  Zbl0689.68056
  12. M. Karpinski and W. Rytter, Fast parallel algorithms for graph matching problems. Oxford University Press, preprint (to appear).  Zbl0895.05050
  13. 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
  14. Y.D. Liang, Finding a maximum matching in a circular-arc graph. Inform. Process. Lett.35 (1993) 185-193.  Zbl0768.68159
  15. L. Lovasz and M. Plummer, Matching Theory. Elsevier Science Publishers (1986).  
  16. S. Micali and V.V. Vazirani, An O ( | V | 1 2 | E | ) algorithm for finding maximum matchings in general graphs, 21 th FOCS (1980) 17-23.  
  17. G.L. Miller and J. Naor, Flow in planar graphs with multiply sources and sinks, Proc. 30 th FOCS (1989) 112-117.  
  18. A. Moitra and R. Jonhson, Parallel algorithms for maximum matching and other problems in interval graphs, TR 88-927. Cornell University (1988).  
  19. K. Mulmuley, U.V. Vazirani and V.V. Vazirani, Matching is as easy as matrix inversion. Combinatorica7 (1987) 105-113.  Zbl0632.68041
  20. T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms. North-Holland (1988).  Zbl0647.05001
  21. O. Ore, The four color problem. Academic Press, New York (1967).  Zbl0149.21101
  22. 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
  23. S.V. Ramachandran and J.H. Reif, An optimal parallel algorithm for graph planarity, 30 th FOCS (1989) 282-287.  
  24. M.O. Rabin, Maximum matching in general graphs through randomization. J. Algorithms10 (1989) 557-567.  Zbl0689.68092
  25. 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
  26. V.V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the O ( V E ) general graph maximum matching algorithm. Combinatorica14 (1994) 71-109.  Zbl0806.05058

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.