Abstract
For planar graphs, counting the number of perfect matchings (and hence determining whether there exists a perfect matching) can be done in NC [4,10]. For planar bipartite graphs, finding a perfect matching when one exists can also be done in NC [8,7]. However in general planar graphs (when the bipartite condition is removed), no NC algorithm for constructing a perfect matching is known.
We address a relaxation of this problem. We consider the fractional matching polytope \(\mathbb{{\cal P}}(G)\) of a planar graph G. Each vertex of this polytope is either a perfect matching, or a half-integral solution: an assignment of weights from the set {0,1/2,1} to each edge of G so that the weights of edges incident on each vertex of G add up to 1 [6]. We show that a vertex of this polytope can be found in NC, provided G has at least one perfect matching to begin with. If, furthermore, the graph is bipartite, then all vertices are integral, and thus our procedure actually finds a perfect matching without explicitly exploiting the bipartiteness of G.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Dahlhaus, E., Karpinski, M.: Perfect matching for regular graphs is AC0-hard for the general matching problem. Journal of Computer and System Sciences 44(1), 94–102 (1992)
Karp, R.M., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random NC. Combinatorica 6, 35–48 (1986)
Karpinski, M., Rytter, W.: Fast parallel algorithms for graph matching problems. Oxford Lecture Series in Mathematics and its Applications, vol. 9. Oxford University Press, Oxford (1998)
Kastelyn, P.W.: Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp. 43–110. Academic Press, London (1967)
Lovasz, L.: On determinants, matchings and random algorithms. In: Budach, L. (ed.) Proceedings of Conference on Fundamentals of Computing Theory, pp. 565–574. Akademia-Verlag (1979)
Lovasz, L., Plummer, M.: Matching Theory. Annals of Discrete Mathematics, vol. 29. North-Holland, Amsterdam (1986)
Mahajan, M., Varadarajan, K.: A new NC-algorithm for finding a perfect matching in planar and bounded genus graphs. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pp. 351–357 (2000)
Miller, G., Naor, J.: Flow in planar graphs with multiple sources and sinks. SIAM Journal on Computing 24, 1002–1017 (1995)
Mulmuley, K., Vazirani, U., Vazirani, V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105–131 (1987)
Vazirani, V.: NC algorithms for computing the number of perfect matchings in K3,3- free graphs and related problems. Information and Computation 80(2), 152–164 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kulkarni, R., Mahajan, M. (2004). Seeking a Vertex of the Planar Matching Polytope in NC. In: Albers, S., Radzik, T. (eds) Algorithms – ESA 2004. ESA 2004. Lecture Notes in Computer Science, vol 3221. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30140-0_43
Download citation
DOI: https://doi.org/10.1007/978-3-540-30140-0_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23025-0
Online ISBN: 978-3-540-30140-0
eBook Packages: Springer Book Archive