Document Open Access Logo

Dynamic Meta-Theorems for Distance and Matching

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.118.pdf
  • Filesize: 0.81 MB
  • 20 pages

Document Identifiers

Author Details

Samir Datta
  • Chennai Mathematical Institute, India
Chetan Gupta
  • Aalto University, Finland
Rahul Jain
  • Fernuniversität in Hagen, Germany
Anish Mukherjee
  • University of Warsaw, Poland
  • IDEAS NCBR, 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: Partally 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.

Acknowledgements

SD and AM would like to thank Nils Vortmeier and Thomas Zeume for their comments on Section 7.

Cite AsGet BibTex

Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, and Raghunath Tewari. Dynamic Meta-Theorems for Distance and Matching. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 118:1-118:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.118

Abstract

Reachability, distance, and matching are some of the most fundamental graph problems that have been of particular interest in dynamic complexity theory in recent years [Samir Datta et al., 2018; Samir Datta et al., 2018; Samir Datta et al., 2020]. Reachability can be maintained with first-order update formulas, or equivalently in DynFO in general graphs with n nodes [Samir Datta et al., 2018], even under O(log(n)/log log(n)) changes per step [Samir Datta et al., 2018]. In the context of how large the number of changes can be handled, it has recently been shown [Samir Datta et al., 2020] that under a polylogarithmic number of changes, reachability is in DynFOpar in planar, bounded treewidth, and related graph classes - in fact in any graph where small non-zero circulation weights can be computed in NC. We continue this line of investigation and extend the meta-theorem for reachability to distance and bipartite maximum matching with the same bounds. These are amongst the most general classes of graphs known where we can maintain these problems deterministically without using a majority quantifier and even maintain witnesses. For the bipartite matching result, modifying the approach from [Stephen A. Fenner et al., 2016], we convert the static non-zero circulation weights to dynamic matching-isolating weights. While reachability is in DynFOar under O(log(n)/log log(n)) changes, no such bound is known for either distance or matching in any non-trivial class of graphs under non-constant changes. We show that, in the same classes of graphs as before, bipartite maximum matching is in DynFOar under O(log(n)/log log(n)) changes per step. En route to showing this we prove that the rank of a matrix can be maintained in DynFOar, also under O(log(n)/log log(n)) entry changes, improving upon the previous O(1) bound [Samir Datta et al., 2018]. This implies a similar extension for the non-uniform DynFO bound for maximum matching in general graphs and an alternate algorithm for maintaining reachability under O(log(n)/log log(n)) changes [Samir Datta et al., 2018].

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
  • Theory of computation → Finite Model Theory
Keywords
  • Dynamic Complexity
  • Distance
  • Matching
  • Derandomization
  • Isolation
  • Matrix Rank

Metrics

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

Related Versions

References

  1. Eric Allender, Robert Beals, and Mitsunori Ogihara. The complexity of matrix rank and feasible systems of linear equations. Comput. Complex., 8(2):99-126, 1999. Google Scholar
  2. David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within nc¹. J. Comput. Syst. Sci., 41(3):274-306, 1990. Google Scholar
  3. 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.
  4. 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, December 15-17, 2021, Virtual Conference, volume 213 of LIPIcs, pages 16:1-16:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  5. Samir Datta, William Hesse, and Raghav Kulkarni. Dynamic complexity of directed reachability and other problems. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 356-367. Springer, 2014. Google Scholar
  6. 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, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, pages 21:1-21:13, 2018. Google Scholar
  7. Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 of Lecture Notes in Computer Science, pages 159-170. Springer, 2015. Google Scholar
  8. Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO. J. ACM, 65(5):33:1-33:24, 2018. Google Scholar
  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. Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. A strategy for dynamic programs: Start over and muddle through. Log. Methods Comput. Sci., 15(2), 2019. Google Scholar
  13. Samir Datta, Anish Mukherjee, Nils Vortmeier, and Thomas Zeume. Reachability and distances under multiple changes. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 120:1-120:14, 2018. Google Scholar
  14. Guozhu Dong, Jianwen Su, and Rodney W. Topor. Nonrecursive incremental evaluation of datalog queries. Ann. Math. Artif. Intell., 14(2-4):187-223, 1995. Google Scholar
  15. 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
  16. Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with O(1) worst case access time. In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 165-169, 1982. Google Scholar
  17. D. A. Harville. Matrix Algebra From a Statistician’s Perspective, volume 8 of Cambridge international series on parallel computation. New York: Springer- Verlag, 2008. Google Scholar
  18. Alexander Healy and Emanuele Viola. Constant-depth circuits for arithmetic in finite fields of characteristic two. In STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, pages 672-683, 2006. Google Scholar
  19. Harold V Henderson and Shayle R Searle. On deriving the inverse of a sum of matrices. Siam Review, 23(1):53-60, 1981. Google Scholar
  20. William Hesse. The dynamic complexity of transitive closure is in DynTC^0. Theor. Comput. Sci., 296(3):473-485, 2003. Google Scholar
  21. 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. Google Scholar
  22. 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. IEEE Computer Society, 2010. Google Scholar
  23. Neil Immerman. Expressibility and parallel complexity. SIAM J. Comput., 18(3):625-638, 1989. Google Scholar
  24. 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
  25. László Lovász. On determinants, matchings, and random algorithms. In FCT, pages 565-574, 1979. Google Scholar
  26. Anish Mukherjee. Static and Dynamic Complexity of Reachability, Matching and Related Problems. PhD thesis, CMI, 2019. 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. Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199-209, 1997. Google Scholar
  29. Raghunath Tewari and N. V. Vinodchandran. Green’s theorem and isolation in planar graphs. Inf. Comput., 215:1-7, 2012. Google Scholar
  30. Wikipedia contributors. Matrix determinant lemma - Wikipedia, the free encyclopedia. https://en.wikipedia.org/wiki/Matrix_determinant_lemma, 2021. [Online; accessed 30-September-2021].
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