Document Open Access Logo

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

Authors Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.43.pdf
  • Filesize: 497 kB
  • 13 pages

Document Identifiers

Author Details

Chetan Gupta
  • Indian Institute of Technology, Kanpur, India
Vimal Raj Sharma
  • Indian Institute of Technology, Kanpur, India
Raghunath Tewari
  • Indian Institute of Technology, Kanpur, India

Funding

  • Gupta, Chetan: Ministry of Electronics and IT, India, VVS PhD program.
  • Sharma, Vimal Raj: Ministry of Electronics and IT, India, VVS PhD program.
  • Tewari, Raghunath: Young Faculty Research Fellowship, Ministry of Electronics and IT, India and INSPIRE Fellowship, Department of Science and Technology, India.

Cite As Get BibTex

Chetan Gupta, Vimal Raj Sharma, and Raghunath Tewari. Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.43

Abstract

We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists. 
As a consequence, we obtain that deciding whether such a graph has a perfect matching or not is in SPL. In 1999, Reinhardt, Allender and Zhou proved that if one can construct a polynomially bounded weight function for a graph in logspace such that it isolates a minimum weight perfect matching in the graph, then the perfect matching problem can be solved in SPL. In this paper, we give a deterministic logspace construction of such a weight function for O(log n) genus bipartite graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Logspace computation
  • High genus
  • Matching isolation

Metrics

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

References

  1. Manindra Agrawal, Thanh Minh Hoang, and Thomas Thierauf. The polynomially bounded perfect matching problem is in NC^2. In STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, pages 489-499, 2007. URL: https://doi.org/10.1007/978-3-540-70918-3_42.
  2. Eric Allender, Klaus Reinhardt, and Shiyu Zhou. Isolation, matching, and counting: Uniform and nonuniform upper bounds. Journal of Computer and System Sciences, 59:164-181, 1999. Google Scholar
  3. Rahul Arora, Ashu Gupta, Rohit Gurjar, and Raghunath Tewari. Derandomizing isolation lemma for k_3, 3-free and k₅-free bipartite graphs. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 10:1-10:15, 2016. Google Scholar
  4. Ashok K. Chandra, Larry J. Stockmeyer, and Uzi Vishkin. Constant depth reducibility. SIAM J. Comput., 13(2):423-439, 1984. URL: https://doi.org/10.1137/0213028.
  5. Samir Datta, Raghav Kulkarni, Raghunath Tewari, and N.V. Vinodchandran. Space complexity of perfect matching in bounded genus bipartite graphs. Journal of Computer and System Sciences, 78(3):765-779, 2012. In Commemoration of Amir Pnueli. URL: https://doi.org/10.1016/j.jcss.2011.11.002.
  6. Jack Edmonds. Paths, trees and flowers. CANADIAN JOURNAL OF MATHEMATICS, pages 449-467, 1965. Google Scholar
  7. Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-NC. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 754-763. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897564.
  8. Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with 0(1) worst case access time. J. ACM, 31(3):538-544, June 1984. URL: https://doi.org/10.1145/828.1884.
  9. Dima Grigoriev and Marek Karpinski. The matching problem for bipartite graphs with polynomially bounded permanents is in NC (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pages 166-172, 1987. URL: https://doi.org/10.1109/SFCS.1987.56.
  10. Chetan Gupta, Vimal Raj Sharma, and Raghunath Tewari. Reachability in o(log n) genus graphs is in unambiguous logspace. In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, pages 34:1-34:13, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.34.
  11. Thanh Minh Hoang. On the matching problem for special graph classes. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pages 139-150, 2010. URL: https://doi.org/10.1109/CCC.2010.21.
  12. Vivek Anand T. Kallampally and Raghunath Tewari. Trading determinism for time in space bounded computations. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, pages 10:1-10:13, 2016. URL: https://doi.org/10.4230/LIPIcs.MFCS.2016.10.
  13. László Lovász. On determinants, matchings, and random algorithms. In FCT, pages 565-574, 1979. Google Scholar
  14. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, 1987. URL: https://doi.org/10.1007/BF02579206.
  15. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM, 55(4), 2008. URL: https://doi.org/10.1145/1391289.1391291.
  16. Klaus Reinhardt and Eric Allender. Making nondeterminism unambiguous. SIAM J. Comput., 29(4):1118-1131, 2000. URL: https://doi.org/10.1137/S0097539798339041.
  17. Ola Svensson and Jakub Tarnawski. The matching problem in general graphs is in quasi-NC. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 696-707. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.70.
  18. Raghunath Tewari and N. V. Vinodchandran. Green’s theorem and isolation in planar graphs. Inf. Comput., 215:1-7, 2012. URL: https://doi.org/10.1016/j.ic.2012.03.002.
  19. Dieter van Melkebeek and Gautam Prakriya. Derandomizing isolation in space-bounded settings. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, pages 5:1-5:32, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.5.
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