Document Open Access Logo

Matroid Intersection: A Pseudo-Deterministic Parallel Reduction from Search to Weighted-Decision

Authors Sumanta Ghosh, Rohit Gurjar

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.41.pdf
  • Filesize: 0.7 MB
  • 16 pages

Document Identifiers

Author Details

Sumanta Ghosh
  • Indian Institute of Technology Bombay, India
Rohit Gurjar
  • Indian Institute of Technology Bombay, India

Acknowledgements

We thank the anonymous reviewers for pointing towards the relevant literature on lattice families.

Cite AsGet BibTex

Sumanta Ghosh and Rohit Gurjar. Matroid Intersection: A Pseudo-Deterministic Parallel Reduction from Search to Weighted-Decision. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.41

Abstract

We study the matroid intersection problem from the parallel complexity perspective. Given two matroids over the same ground set, the problem asks to decide whether they have a common base and its search version asks to find a common base, if one exists. Another widely studied variant is the weighted decision version where with the two matroids, we are given small weights on the ground set elements and a target weight W, and the question is to decide whether there is a common base of weight at least W. From the perspective of parallel complexity, the relation between the search and the decision versions is not well understood. We make a significant progress on this question by giving a pseudo-deterministic parallel (NC) algorithm for the search version that uses an oracle access to the weighted decision. The notion of pseudo-deterministic NC was recently introduced by Goldwasser and Grossman [Shafi Goldwasser and Ofer Grossman, 2017], which is a relaxation of NC. A pseudo-deterministic NC algorithm for a search problem is a randomized NC algorithm that, for a given input, outputs a fixed solution with high probability. In case the given matroids are linearly representable, our result implies a pseudo-deterministic NC algorithm (without the weighted decision oracle). This resolves an open question posed by Anari and Vazirani [Nima Anari and Vijay V. Vazirani, 2020].

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Matroids and greedoids
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Linear Matroid
  • Matroid Intersection
  • Parallel Complexity
  • Pseudo-deterministic NC

Metrics

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

Related Versions

References

  1. Manindra Agrawal, Thanh Minh Hoang, and Thomas Thierauf. The polynomially bounded perfect matching problem is in NC². In 24th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 4393 of Lecture Notes in Computer Science, pages 489-499. Springer Berlin Heidelberg, 2007. URL: https://doi.org/10.1007/978-3-540-70918-3_42.
  2. 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. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.54.
  3. Stuart J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters, 18(3):147-150, 1984. Google Scholar
  4. Allan Borodin, Stephen Cook, and Nicholas Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 58(1-3):113-136, July 1984. Google Scholar
  5. Allan Borodin, Joachim von zur Gathen, and John Hopcroft. Fast parallel matrix and GCD computations. Information and Control, 52(3):241-256, 1982. Google Scholar
  6. Kevin Buchin, David Eppstein, Maarten Löffler, Martin Nöllenburg, and Rodrigo I. Silveira. Adjacency-preserving spatial treemaps. J. Comput. Geom., 7(1):100-122, 2016. URL: https://doi.org/10.20382/jocg.v7i1a6.
  7. Laszlo Csanky. Fast parallel matrix inversion algorithms. SIAM Journal on Computing, 5(4):618-623, 1976. URL: https://doi.org/10.1137/0205040.
  8. Marek Cygan, Harold N. Gabow, and Piotr Sankowski. Algorithmic applications of baur-strassen’s theorem: Shortest cycles, diameter and matchings. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 531-540. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.72.
  9. Marek Cygan, Harold N. Gabow, and Piotr Sankowski. Algorithmic applications of baur-strassen’s theorem: Shortest cycles, diameter, and matchings. J. ACM, 62(4), 2015. URL: https://doi.org/10.1145/2736283.
  10. Elias Dahlhaus and Marek Karpinski. Matching and multidimensional matching in chordal and strongly chordal graphs. Discrete Applied Mathematics, 84(1–3):79-91, 1998. Google Scholar
  11. Samir Datta, Raghav Kulkarni, and Sambuddha Roy. Deterministically isolating a perfect matching in bipartite planar graphs. Theory of Computing Systems, 47:737-757, 2010. URL: https://doi.org/10.1007/s00224-009-9204-8.
  12. Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. Google Scholar
  13. Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and Their Applications, Gordon and Breach, New York, pages 69-87, 1970. Google Scholar
  14. David Eppstein, Elena Mumford, Bettina Speckmann, and Kevin Verbeek. Area-universal and constrained rectangular layouts. SIAM J. Comput., 41(3):537-564, 2012. URL: https://doi.org/10.1137/110834032.
  15. Stephen Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-NC. SIAM Journal on Computing, 0(0):STOC16-218-STOC16-235, 2019. URL: https://doi.org/10.1137/16M1097870.
  16. 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, pages 754-763, 2016. Google Scholar
  17. Eran Gat and Shafi Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. Electronic Colloquium on Computational Complexity (ECCC), 18:136, 2011. URL: http://eccc.hpi-web.de/report/2011/136.
  18. Oded Goldreich, Shafi Goldwasser, and Dana Ron. On the possibilities and limitations of pseudodeterministic algorithms. In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013, pages 127-138. ACM, 2013. URL: https://doi.org/10.1145/2422436.2422453.
  19. Shafi Goldwasser and Ofer Grossman. Bipartite perfect matching in pseudo-deterministic NC. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 87:1-87:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.87.
  20. 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 (FOCS), pages 166-172, 1987. URL: https://doi.org/10.1109/SFCS.1987.56.
  21. Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Identity testing for constant-width, and any-order, read-once oblivious arithmetic branching programs. Theory of Computing, 13(2):1-21, 2017. Google Scholar
  22. Rohit Gurjar and Thomas Thierauf. Linear matroid intersection is in quasi-nc. In 49th Annual ACM Symposium on Theory of Computing, pages 821-830, 2017. Google Scholar
  23. Robert W. Irving, Paul Leather, and Dan Gusfield. An efficient algorithm for the "optimal" stable marriage. J. ACM, 34(3):532-543, 1987. URL: https://doi.org/10.1145/28869.28871.
  24. Richard M. Karp, Eli Upfal, and Avi Wigderson. Constructing a perfect matching is in random NC. Combinatorica, 6(1):35-48, 1986. Google Scholar
  25. Richard M. Karp, Eli Upfal, and Avi Wigderson. The complexity of parallel search. Journal of Computer and System Sciences, 36(2):225-253, 1988. URL: https://doi.org/10.1016/0022-0000(88)90027-X.
  26. László Lovász. On determinants, matchings, and random algorithms. In FCT, volume 79, pages 565-574, 1979. Google Scholar
  27. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7:105-113, 1987. URL: https://doi.org/10.1007/BF02579206.
  28. H. Narayanan, Huzur Saran, and Vijay V. Vazirani. Randomized parallel algorithms for matroid union and intersection, with applications to arboresences and edge-disjoint spanning trees. SIAM J. Comput., 23(2):387-397, 1994. URL: https://doi.org/10.1137/S0097539791195245.
  29. Øystein Ore. Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I, 7(15):27, 1922. Google Scholar
  30. Piotr Sankowski. NC algorithms for weighted planar perfect matching and related problems. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 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. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.97.
  31. Alexander Schrijver. Combinatorial optimization : polyhedra and efficiency. Vol. B. , Matroids, trees, stable sets. chapters 39-69. Algorithms and combinatorics. Springer-Verlag, Berlin, Heidelberg, New York, N.Y., et al., 2003. URL: http://opac.inria.fr/record=b1124843.
  32. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. Google Scholar
  33. Ashok Subramanian. A polynomial bound on the number of light cycles in an undirected graph. Information Processing Letters, 53(4):173-176, 1995. URL: https://doi.org/10.1016/0020-0190(94)00202-A.
  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 2017, Berkeley, CA, USA, October 15-17, 2017, pages 696-707, 2017. URL: https://doi.org/10.1109/FOCS.2017.70.
  35. Raghunath Tewari and N. V. Vinodchandran. Green’s theorem and isolation in planar graphs. Information and Computation, 215:1-7, 2012. URL: https://doi.org/10.1016/j.ic.2012.03.002.
  36. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, EUROSAM '79, pages 216-226, 1979. 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