×
Datta, Samir; Kulkarni, Raghav; Kumar, Ashish; Mukherjee, Anish

Planar maximum matching: towards a parallel algorithm. (English) Zbl 1533.68227

Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 21, 13 p. (2018).
Summary: Perfect matchings in planar graphs have been extensively studied and understood in the context of parallel complexity [P. W. Kasteleyn, in: Graph theory and theoretical physics, 43–110 (1967; Zbl 0205.28402); V. V. Vazirani, Lect. Notes Comput. Sci. 318, 233–242 (1988; Zbl 0651.68086); M. Mahajan and K. R. Varadarajan, STOC 2000, 351–357 (2000; Zbl 1296.05187); S. Datta et al., Theory Comput. Syst. 47, No. 3, 737–757 (2010; Zbl 1206.68231); N. Anari and V. V. Vazirani, J. ACM 67, No. 4, Article No. 21, 34 p. (2020; Zbl 1491.68131)]. However, corresponding results for maximum matchings have been elusive. We partly bridge this gap by proving:
1)
An SPL upper bound for planar bipartite maximum matching search.
2)
Planar maximum matching search reduces to planar maximum matching decision.
3)
Planar maximum matching count reduces to planar bipartite maximum matching count and planar maximum matching decision.
The first bound improves on the known [Thanh Minh Hoang, CCC 2010, 139–150 (2010; doi:10.1109/CCC.2010.21)] bound of \(\textbf{L}^{\textbf{C}_=\textbf{L}}\) and is adaptable to any special bipartite graph class with non-zero circulation such as bounded genus graphs, \(K_{3,3}\)-free graphs and \(K_5\)-free graphs. Our bounds and reductions non-trivially combine techniques like the Gallai-Edmonds decomposition [L. Lovász and M. D. Plummer, Matching theory. Amsterdam: Elsevier (1986; Zbl 0618.05001)], deterministic isolation [Datta et al., loc. cit.; S. Datta et al., J. Comput. Syst. Sci. 78, No. 3, 765–779 (2012; Zbl 1253.68168); R. Arora et al., LIPIcs – Leibniz Int. Proc. Inform. 47, Article 10, 15 p. (2016; Zbl 1388.68208)], and the recent breakthroughs in the parallel search for planar perfect matchings [Anari and Vazirani, loc. cit.; P. Sankowski, LIPIcs – Leibniz Int. Proc. Inform. 107, Article 97, 16 p. (2018; Zbl 1499.68287)].
For the entire collection see [Zbl 1407.68036].

Cited in 1 Document

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C10 Planar graphs; geometric and topological aspects of graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68W10 Parallel algorithms in computer science

Keywords:

maximum matching; planar graphs; parallel complexity; reductions

Citations:

Zbl 0651.68086; Zbl 1296.05187; Zbl 1206.68231; Zbl 0618.05001; Zbl 1253.68168; Zbl 1388.68208; Zbl 1491.68131; Zbl 1499.68287; Zbl 0205.28402
Cite Review PDF
Full Text: DOI

References:

[1] E. Allender, K. Reinhardt, and S. Zhou. Isolation, Matching, and Counting: Uniform and Nonuniform Upper Bounds. Journal of Computer and System Sciences, 59:164-181, 1999. · Zbl 0944.68068
[2] Nima Anari and Vijay V. Vazirani. Planar Graph Perfect Matching is in NC. CoRR, abs/1709.07822, 2017. · Zbl 1491.68131
[3] Rahul Arora, Ashu Gupta, Rohit Gurjar, and Raghunath Tewari. Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS, pages 10:1-10:15, 2016. · Zbl 1388.68208
[4] Samir Datta, Raghav Kulkarni, Nutan Limaye, and Meena Mahajan. Planarity, Determ-inants, Permanents, and (Unique) Matchings. ACM Trans. Comput. Theory, 1(3):1-20, 2010. · Zbl 1322.05088
[5] Samir Datta, Raghav Kulkarni, and Anish Mukherjee. Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS, pages 28:1-28:12, 2016. · Zbl 1398.05163
[6] Samir Datta, Raghav Kulkarni, and Sambuddha Roy. Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs. Theory of Computing Systems, 47:737-757, 2010. · Zbl 1206.68231
[7] Samir Datta, Raghav Kulkarni, Raghunath Tewari, and N. V. Vinodchandran. Space complexity of perfect matching in bounded genus bipartite graphs. J. Comput. Syst. Sci., 78(3):765-779, 2012. · Zbl 1253.68168
[8] J. Edmonds. Paths, Trees and Flowers. Canad. J. Math., 17:449-467, 1965. · Zbl 0132.20903
[9] David Eppstein and Vijay V. Vazirani. NC algorithms for perfect matching and maximum flow in one-crossing-minor-free graphs. CoRR, abs/1802.00084, 2018.
[10] Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-NC. In 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 754-763, 2016. · Zbl 1373.68267
[11] Anna Galluccio and Martin Loebl. On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents. Electr. J. Comb., 6, 1999. · Zbl 0909.05006
[12] Eran Gat and Shafi Goldwasser. Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications. Electronic Colloquium on Computational Complexity (ECCC), 18:136, 2011.
[13] Oded Goldreich, Shafi Goldwasser, and Dana Ron. On the possibilities and limitations of pseudodeterministic algorithms. In Innovations in Theoretical Computer Science, ITCS, pages 127-138, 2013. · Zbl 1361.68089
[14] Shafi Goldwasser and Ofer Grossman. Bipartite Perfect Matching in Pseudo-Deterministic NC. In 44th International Colloquium on Automata, Languages, and Programming, ICALP, pages 87:1-87:13, 2017. · Zbl 1442.68167
[15] Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden. Pseudo-Deterministic Proofs. In 9th Innovations in Theoretical Computer Science Conference, ITCS, pages 17:1-17:18, 2018. · Zbl 1462.68049
[16] Ofer Grossman. Finding Primitive Roots Pseudo-Deterministically. Electronic Colloquium on Computational Complexity (ECCC), page 207, 2015.
[17] Ofer Grossman and Yang P. Liu. Reproducibility and Pseudo-Determinism in Log-Space. CoRR, abs/1803.04025, 2018. · Zbl 1431.68138
[18] Thanh Minh Hoang. On the Matching Problem for Special Graph Classes. In IEEE Conference on Computational Complexity, pages 139-150, 2010. doi:10.1109/CCC.2010. 21. · doi:10.1109/CCC.2010.21
[19] Stefan Hougardy and Doratha E. Drake Vinkemeier. Approximating weighted matchings in parallel. Inf. Process. Lett., 99(3):119-123, 2006. · Zbl 1184.68638
[20] Marek Karpinski and Wojciech Rytter. Fast parallel algorithms for graph matching prob-lems, volume 9 of Oxford Lecture Series in Mathematics and its Applications. The Clarendon Press, Oxford University Press, New York, 1998. · Zbl 0895.05050
[21] P W Kastelyn. Graph Theory and Crystal Physics. In F Harary, editor, Graph Theory and Theoretical Physics, pages 43-110. Academic Press, 1967. · Zbl 0205.28402
[22] Raghav Kulkarni, Meena Mahajan, and Kasturi R. Varadarajan. Some perfect match-ings and perfect half-integral matchings in NC. Chicago Journal of Theoretical Computer Science, 2008(4), September 2008. · Zbl 1286.05052
[23] L. Lovász and M.D. Plummer. Matching Theory, volume 29. North-Holland Publishing Co, 1986. · Zbl 0618.05001
[24] Meena Mahajan, P. R. Subramanya, and V. Vinay. The combinatorial approach yields an NC algorithm for computing Pfaffians. Discrete Applied Mathematics, 143(1-3):1-16, 2004. · Zbl 1053.05081
[25] Meena Mahajan and Kasturi R. Varadarajan. A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs. In STOC, pages 351-357, 2000. · Zbl 1296.05187
[26] Meena Mahajan and V. Vinay. Determinant: Combinatorics, Algorithms, and Complexity. Chicago J. Theor. Comput. Sci., 1997. · Zbl 0924.68088
[27] Silvio Micali and Vijay V. Vazirani. An O(sqrt(|v|) |E|) Algorithm for Finding Maximum Matching in General Graphs. In 21st Annual Symposium on Foundations of Computer Science, pages 17-27, 1980.
[28] Gary L. Miller and Joseph Naor. Flow in Planar Graphs with Multiple Sources and Sinks. SIAM J. Comput., 24(5):1002-1017, 1995. · Zbl 0836.68087
[29] Ketan Mulmuley, Umesh Vazirani, and Vijay Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7:105-113, 1987. · Zbl 0632.68041
[30] Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity -Graphs, Structures, and Al-gorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. · Zbl 1268.05002
[31] Igor Carboni Oliveira and Rahul Santhanam. Pseudodeterministic constructions in subex-ponential time. In 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 665-677, 2017. · Zbl 1370.68326
[32] Piotr Sankowski. NC algorithms for weighted planar perfect matching and related problems. In 45th International Colloquium on Automata, Languages, and Programming, ICALP, pages 97:1-97:16, 2018. · Zbl 1499.68287
[33] Simon Straub, Thomas Thierauf, and Fabian Wagner. Counting the Number of Perfect Matchings in K 5-Free Graphs. Theory Comput. Syst., 59(3):416-439, 2016. · Zbl 1353.05100
[34] Ola Svensson and Jakub Tarnawski. The Matching Problem in General Graphs Is in Quasi-NC. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 696-707, 2017.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.