Document Open Access Logo

Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles

Authors Samir Datta, Kishlaya Jaiswal

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.36.pdf
  • Filesize: 0.74 MB
  • 22 pages

Document Identifiers

Author Details

Samir Datta
  • Chennai Mathematical Institute, India
Kishlaya Jaiswal
  • Chennai Mathematical Institute, India

Funding

  • Datta, Samir: Partially funded by a grant from Infosys foundation and SERB-MATRICS grant MTR/2017/000480.

Acknowledgements

We would like to thank Eric Allender for a discussion regarding what was known about field operations in ⨁L. We would also like to thank Partha Mukhopadhyay for his comments on a preliminary version of the paper. We thank the anonymous referees for helping us improve the presentation of the paper.

Cite AsGet BibTex

Samir Datta and Kishlaya Jaiswal. Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.36

Abstract

We present a parallel algorithm for permanent mod 2^k of a matrix of univariate integer polynomials. It places the problem in ⨁L ⊆ NC². This extends the techniques of Valiant [Leslie G. Valiant, 1979], Braverman, Kulkarni and Roy [Mark Braverman et al., 2009] and Björklund and Husfeldt [Andreas Björklund and Thore Husfeldt, 2019] and yields a (randomized) parallel algorithm for shortest two disjoint paths improving upon the recent (randomized) polynomial time algorithm [Andreas Björklund and Thore Husfeldt, 2019]. We also recognize the disjoint paths problem as a special case of finding disjoint cycles, and present (randomized) parallel algorithms for finding a shortest cycle and shortest two disjoint cycles passing through any given fixed number of vertices or edges.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parallel algorithms
Keywords
  • permanent mod powers of 2
  • parallel computation
  • graphs
  • shortest disjoint paths
  • shortest disjoint cycles

Metrics

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

Related Versions

References

  1. Andreas Björklund and Thore Husfeldt. Counting shortest two disjoint paths in cubic planar graphs with an NC 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 19:1-19:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.19.
  2. Andreas Björklund and Thore Husfeldt. Shortest two disjoint paths in polynomial time. SIAM J. Comput., 48(6):1698-1710, 2019. URL: https://doi.org/10.1137/18M1223034.
  3. Mark Braverman, Raghav Kulkarni, and Sambuddha Roy. Space-efficient counting in graphs on surfaces. Comput. Complex., 18(4):601-649, 2009. URL: https://doi.org/10.1007/s00037-009-0266-4.
  4. Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 197-206. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.29.
  5. Carsten Damm. Problems complete for parityl. Information Processing Letters, 36(5):247-250, 1990. URL: https://doi.org/10.1016/0020-0190(90)90150-V.
  6. Samir Datta, Siddharth Iyer, Raghav Kulkarni, and Anish Mukherjee. Shortest k-disjoint paths via determinants. In Sumit Ganguly and Paritosh K. Pandya, editors, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, December 11-13, 2018, Ahmedabad, India, volume 122 of LIPIcs, pages 19:1-19:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.19.
  7. Éric Colin de Verdière and Alexander Schrijver. Shortest vertex-disjoint two-face paths in planar graphs. ACM Trans. Algorithms, 7(2):19:1-19:12, 2011. URL: https://doi.org/10.1145/1921659.1921665.
  8. W. Eberly. Very fast parallel matrix and polynomial arithmetic. In 25th Annual Symposium onFoundations of Computer Science, 1984., pages 21-30, 1984. URL: https://doi.org/10.1109/SFCS.1984.715897.
  9. W. Eberly. Efficient parallel independent subsets and matrix factorizations. In Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, pages 204-211, 1991. URL: https://doi.org/10.1109/SPDP.1991.218278.
  10. Faith E. Fich and Martin Tompa. The parallel complexity of exponentiating polynomials over finite fields. J. ACM, 35(3):651–667, 1988. URL: https://doi.org/10.1145/44483.44496.
  11. Steven Fortune, John E. Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10:111-121, 1980. URL: https://doi.org/10.1016/0304-3975(80)90009-2.
  12. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci., 65(4):695-716, 2002. URL: https://doi.org/10.1016/S0022-0000(02)00025-9.
  13. Hiroshi Hirai and Hiroyuki Namba. Shortest (a+b)-path packing via hafnian. Algorithmica, 80(8):2478-2491, 2018. URL: https://doi.org/10.1007/s00453-017-0334-0.
  14. Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, USA, 2nd edition, 2012. Google Scholar
  15. Ce Jin, Nikhil Vyas, and Ryan Williams. Fast low-space algorithms for subset sum. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1757-1776. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.106.
  16. James F. Lynch. The equivalence of theorem proving and the interconnection problem. SIGDA Newsl., 5(3):31–36, 1975. URL: https://doi.org/10.1145/1061425.1061430.
  17. Meena Mahajan, P. R. Subramanya, and V. Vinay. The combinatorial approach yields an _nc algorithm for computing pfaffians. Discret. Appl. Math., 143(1-3):1-16, 2004. URL: https://doi.org/10.1016/j.dam.2003.12.001.
  18. Meena Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. Chic. J. Theor. Comput. Sci., 1997, 1997. URL: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html.
  19. Ketan Mulmuley. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Comb., 7(1):101-104, 1987. URL: https://doi.org/10.1007/BF02579205.
  20. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, page 345–354, New York, NY, USA, 1987. Association for Computing Machinery. URL: https://doi.org/10.1145/28395.383347.
  21. Klaus Reinhardt and Eric Allender. Making nondeterminism unambiguous. SIAM J. Comput., 29(4):1118-1131, 2000. URL: https://doi.org/10.1137/S0097539798339041.
  22. Heike Ripphausen-Lipa, Dorothea Wagner, and Karsten Weihe. Linear-time algorithms for disjoint two-face paths problems in planar graphs. Int. J. Found. Comput. Sci., 7(2):95-110, 1996. URL: https://doi.org/10.1142/S0129054196000087.
  23. N. Robertson and P.D. Seymour. Graph minors .xiii. the disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1006.
  24. Alexander Schrijver. Finding k disjoint paths in a directed planar graph. SIAM J. Comput., 23(4):780-788, 1994. URL: https://doi.org/10.1137/S0097539792224061.
  25. Hitoshi Suzuki, Takehiro Akama, and Takao Nishizeki. Finding steiner forests in planar graphs. In David S. Johnson, editor, Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1990, San Francisco, California, USA, pages 444-453. SIAM, 1990. URL: http://dl.acm.org/citation.cfm?id=320176.320230.
  26. Leslie G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189-201, 1979. URL: https://doi.org/10.1016/0304-3975(79)90044-6.
  27. J.H. van Lint. Introduction to Coding Theory. Graduate Texts in Mathematics. Springer Berlin Heidelberg, 2013. URL: https://books.google.co.in/books?id=6dbqCAAAQBAJ.
  28. Magnus Wahlström. Abusing the tutte matrix: An algebraic instance compression for the k-set-cycle problem. In STACS, pages 341-352, 2013. Google Scholar
  29. Viktória Zankó. #p-completeness via many-one reductions. Int. J. Found. Comput. Sci., 2(1):77-82, 1991. URL: https://doi.org/10.1142/S0129054191000066.
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