Document Open Access Logo

Planar Maximum Matching: Towards a Parallel Algorithm

Authors Samir Datta, Raghav Kulkarni, Ashish Kumar, Anish Mukherjee

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.21.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Samir Datta
  • Chennai Mathematical Institute & UMI ReLaX, Chennai, India
Raghav Kulkarni
  • Chennai Mathematical Institute, Chennai, India
Ashish Kumar
  • Chennai Mathematical Institute, Chennai, India
Anish Mukherjee
  • Chennai Mathematical Institute, Chennai, India

Funding

  • Datta, Samir: The author was partially funded by a grant from Infosys foundation and SERB grant MTR/2017/000480.
  • Mukherjee, Anish: The author was partially supported by a grant from Infosys foundation and TCS PhD fellowship.

Cite As Get BibTex

Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee. Planar Maximum Matching: Towards a Parallel Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.21

Abstract

Perfect matchings in planar graphs have been extensively studied and understood in the context of parallel complexity [P W Kastelyn, 1967; Vijay Vazirani, 1988; Meena Mahajan and Kasturi R. Varadarajan, 2000; Datta et al., 2010; Nima Anari and Vijay V. Vazirani, 2017]. 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, 2010] bound of L^{C_=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, 1986], deterministic isolation [Datta et al., 2010; Samir Datta et al., 2012; Rahul Arora et al., 2016], and the recent breakthroughs in the parallel search for planar perfect matchings [Nima Anari and Vijay V. Vazirani, 2017; Piotr Sankowski, 2018].

Subject Classification

ACM Subject Classification
  • Theory of computation → Parallel algorithms
Keywords
  • maximum matching
  • planar graphs
  • parallel complexity
  • reductions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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. Google Scholar
  2. Nima Anari and Vijay V. Vazirani. Planar Graph Perfect Matching is in NC. CoRR, abs/1709.07822, 2017. Google Scholar
  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. Google Scholar
  4. Samir Datta, Raghav Kulkarni, Nutan Limaye, and Meena Mahajan. Planarity, Determinants, Permanents, and (Unique) Matchings. ACM Trans. Comput. Theory, 1(3):1-20, 2010. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  8. J. Edmonds. Paths, Trees and Flowers. Canad. J. Math., 17:449-467, 1965. Google Scholar
  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. Google Scholar
  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. Google Scholar
  11. Anna Galluccio and Martin Loebl. On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents. Electr. J. Comb., 6, 1999. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  16. Ofer Grossman. Finding Primitive Roots Pseudo-Deterministically. Electronic Colloquium on Computational Complexity (ECCC), page 207, 2015. Google Scholar
  17. Ofer Grossman and Yang P. Liu. Reproducibility and Pseudo-Determinism in Log-Space. CoRR, abs/1803.04025, 2018. Google Scholar
  18. Thanh Minh Hoang. On the Matching Problem for Special Graph Classes. In IEEE Conference on Computational Complexity, pages 139-150, 2010. URL: http://dx.doi.org/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. Google Scholar
  20. Marek Karpinski and Wojciech Rytter. Fast parallel algorithms for graph matching problems, volume 9 of Oxford Lecture Series in Mathematics and its Applications. The Clarendon Press, Oxford University Press, New York, 1998. Google Scholar
  21. P W Kastelyn. Graph Theory and Crystal Physics. In F Harary, editor, Graph Theory and Theoretical Physics, pages 43-110. Academic Press, 1967. Google Scholar
  22. Raghav Kulkarni, Meena Mahajan, and Kasturi R. Varadarajan. Some perfect matchings and perfect half-integral matchings in NC. Chicago Journal of Theoretical Computer Science, 2008(4), September 2008. Google Scholar
  23. L. Lovász and M.D. Plummer. Matching Theory, volume 29. North-Holland Publishing Co, 1986. Google Scholar
  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. Google Scholar
  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. Google Scholar
  26. Meena Mahajan and V. Vinay. Determinant: Combinatorics, Algorithms, and Complexity. Chicago J. Theor. Comput. Sci., 1997. Google Scholar
  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. Google Scholar
  28. Gary L. Miller and Joseph Naor. Flow in Planar Graphs with Multiple Sources and Sinks. SIAM J. Comput., 24(5):1002-1017, 1995. Google Scholar
  29. Ketan Mulmuley, Umesh Vazirani, and Vijay Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7:105-113, 1987. Google Scholar
  30. Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. Google Scholar
  31. Igor Carboni Oliveira and Rahul Santhanam. Pseudodeterministic constructions in subexponential time. In 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 665-677, 2017. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  35. L. G. Valiant. The Complexity of Computing the Permanent. Theor. Comput. Sci., 8:189-201, 1979. Google Scholar
  36. Vijay Vazirani. NC algorithms for computing the number of perfect matchings in k_3,3-free graphs and related problems. In Proceedings of SWAT '88, pages 233-242, 1988. Google Scholar
  37. Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2 edition, September 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact