Document Open Access Logo

Reachability and Matching in Single Crossing Minor Free Graphs

Authors Samir Datta, Chetan Gupta, Rahul Jain , Anish Mukherjee , Vimal Raj Sharma, Raghunath Tewari

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.16.pdf
  • Filesize: 0.79 MB
  • 16 pages

Document Identifiers

Author Details

Samir Datta
  • Chennai Mathematical Institute, Chennai, India
Chetan Gupta
  • Aalto University, Finland
Rahul Jain
  • Fernuniversität in Hagen, Germany
Anish Mukherjee
  • Institute of Informatics, University of Warsaw, Poland
Vimal Raj Sharma
  • Indian Institute of Technology, Kanpur, India
Raghunath Tewari
  • Indian Institute of Technology, Kanpur, India

Funding

  • Datta, Samir: Partially funded by a grant from Infosys foundation and SERB-MATRICS grant MTR/2017/000480.
  • Gupta, Chetan: Supported by Academy of Finland, Grant 321901.
  • Mukherjee, Anish: Supported by the ERC CoG grant TUgbOAT no 772346.
  • Sharma, Vimal Raj: Ministry of Electronics and IT, India, VVS PhD program.
  • Tewari, Raghunath: Young Faculty Research Fellowship, Ministry of Electronics and IT, India.

Cite AsGet BibTex

Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, and Raghunath Tewari. Reachability and Matching in Single Crossing Minor Free Graphs. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.16

Abstract

We show that for each single crossing graph H, a polynomially bounded weight function for all H-minor free graphs G can be constructed in logspace such that it gives nonzero weights to all the cycles in G. This class of graphs subsumes almost all classes of graphs for which such a weight function is known to be constructed in logspace. As a consequence, we obtain that for the class of H-minor free graphs where H is a single crossing graph, reachability can be solved in UL, and bipartite maximum matching can be solved in SPL, which are small subclasses of the parallel complexity class NC. In the restrictive case of bipartite graphs, our maximum matching result improves upon the recent result of Eppstein and Vazirani [David Eppstein and Vijay V. Vazirani, 2021], where they show an NC bound for constructing perfect matching in general single crossing minor free graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
Keywords
  • Reachability
  • Matching
  • Logspace
  • Single-crossing minor free graphs

Metrics

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

References

  1. Eric Allender and Meena Mahajan. The complexity of planarity testing. Information and Computation, 189:117-134, 2004. Google Scholar
  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. Nima Anari and Vijay V. Vazirani. Matching is as easy as the decision problem, in the NC model. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 54:1-54:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  4. Nima Anari and Vijay V. Vazirani. Planar graph perfect matching is in nc. J. ACM, 67(4), May 2020. URL: https://doi.org/10.1145/3397504.
  5. 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, France, pages 10:1-10:15, 2016. Google Scholar
  6. Chris Bourke, Raghunath Tewari, and N. V. Vinodchandran. Directed planar reachability is in unambiguous log-space. ACM Transactions on Computation Theory, 1(1):1-17, 2009. URL: https://doi.org/10.1145/1490270.1490274.
  7. Erin W. Chambers and David Eppstein. Flows in one-crossing-minor-free graphs. J. Graph Algorithms Appl., 17(3):201-220, 2013. Google Scholar
  8. Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee. Planar maximum matching: Towards a parallel algorithm. In Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao, editors, 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, volume 123 of LIPIcs, pages 21:1-21:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.21.
  9. Samir Datta, Raghav Kulkarni, and Sambuddha Roy. Deterministically isolating a perfect matching in bipartite planar graphs. Theory Comput. Syst., 47(3):737-757, 2010. Google Scholar
  10. 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.
  11. Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, and Thomas Zeume. Dynamic complexity of reachability: How many changes can we handle? In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), pages 122:1-122:19, 2020. Google Scholar
  12. Erik D. Demaine, Mohammad Taghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos. Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci., 69(2):166-195, 2004. Google Scholar
  13. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959. Google Scholar
  14. Jack Edmonds. Paths, trees and flowers. Canadian Journal Of Mathematics, pages 449-467, 1965. Google Scholar
  15. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of bodlaender and courcelle. In FOCS '10: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, 2010. URL: http://www.eccc.uni-trier.de/report/2010/062/.
  16. David Eppstein and Vijay V. Vazirani. NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs. SIAM J. Comput., 50(3):1014-1033, 2021. Google Scholar
  17. Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in Quasi-NC. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 754-763, 2016. Google Scholar
  18. L. R. Ford, Jr. and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399-404, 1956. URL: https://doi.org/10.4153/CJM-1956-045-5.
  19. 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. Google Scholar
  20. Chetan Gupta, Vimal Raj Sharma, and Raghunath Tewari. Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs. In Javier Esparza and Daniel Krá?, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1-43:13, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. Google Scholar
  21. 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. Google Scholar
  22. Richard M. Karp, Eli Upfal, and Avi Wigderson. Constructing a perfect matching is in random NC. In Robert Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 22-32. ACM, 1985. Google Scholar
  23. Arpita Korwar. Matching in planar graphs. Master’s thesis, IITK, 2009. Google Scholar
  24. Jan Kynčl and Tomáš Vyskočil. Logspace reduction of directed reachability for bounded genus graphs to the planar case. ACM Transactions on Computation Theory, 1(3):1-11, 2010. URL: https://doi.org/10.1145/1714450.1714451.
  25. Meena Mahajan and Kasturi R. Varadarajan. A new nc-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract). In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC '00, pages 351-357, New York, NY, USA, 2000. ACM. URL: https://doi.org/10.1145/335305.335346.
  26. Gary L. Miller and Joseph Naor. Flow in planar graphs with multiple sources and sinks. SIAM Journal on Computing, 24:1002-1017, 1995. Google Scholar
  27. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 345-354, 1987. Google Scholar
  28. Klaus Reinhardt and Eric Allender. Making nondeterminism unambiguous. SIAM J. Comput., 29(4):1118-1131, 2000. Google Scholar
  29. Neil Robertson and Paul D. Seymour. Excluding a graph with one crossing. In Graph Structure Theory, Proceedings of a AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, June 22 to July 5, 1991, Seattle, USA, pages 669-675, 1991. Google Scholar
  30. Piotr Sankowski. NC algorithms for weighted planar perfect matching and related problems. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 97:1-97:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  31. Simon Straub, Thomas Thierauf, and Fabian Wagner. Counting the number of perfect matchings in K₅-free graphs. Theory Comput. Syst., 59(3):416-439, 2016. Google Scholar
  32. 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 2017, Berkeley, CA, USA, pages 696-707. IEEE Computer Society, 2017. Google Scholar
  33. Raghunath Tewari and N. V. Vinodchandran. Green’s theorem and isolation in planar graphs. Inf. Comput., 215:1-7, 2012. Google Scholar
  34. Thomas Thierauf and Fabian Wagner. Reachability in K_3,3-free Graphs and K₅-free Graphs is in Unambiguous Log-Space. In 17th International Conference on Foundations of Computation Theory (FCT), Lecture Notes in Computer Science 5699, pages 323-334. Springer-Verlag, 2009. Google Scholar
  35. Thomas Thierauf and Fabian Wagner. The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. Theory Comput. Syst., 47(3):655-673, 2010. 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 Imprint Privacy Contact