Dynamic Meta-Theorems for Distance and Matching

49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022, pp. 1-20, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 229

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 [8, 13, 11]. Reachability can be maintained with first-order update formulas, or equivalently in DynFO in general graphs with n nodes [8], even under (Equation presented) changes per step [13]. In the context of how large the number of changes can be handled, it has recently been shown [11] that under a polylogarithmic number of changes, reachability is in DynFO[⊕](≤, +, ×) 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 [15], we convert the static non-zero circulation weights to dynamic matching-isolating weights. While reachability is in DynFO(≤, +, ×) under (Equation presented) 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 DynFO(≤, +, ×) under (Equation presented) changes per step. En route to showing this we prove that the rank of a matrix can be maintained in DynFO(≤, +, ×), also under (Equation presented) entry changes, improving upon the previous O(1) bound [8]. 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 (Equation presented) changes [13].

Description

Funding Information: Funding Samir Datta: Partially funded by a grant from Infosys foundation and SERB-MATRICS grant MTR/2017/000480. Chetan Gupta: Supported by Academy of Finland, Grant 321901. Anish Mukherjee: Partally supported by the ERC CoG grant TUgbOAT no 772346. Vimal Raj Sharma: Ministry of Electronics and IT, India, VVS PhD program. Raghunath Tewari: Young Faculty Research Fellowship, Ministry of Electronics and IT, India. Publisher Copyright: © Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, and Raghunath Tewari; licensed under Creative Commons License CC-BY 4.0

Keywords

Derandomization, Distance, Dynamic Complexity, Isolation, Matching, Matrix Rank

DOI

10.4230/LIPIcs.ICALP.2022.118

Citation

Datta, S, Gupta, C, Jain, R, Mukherjee, A, Sharma, V R & Tewari, R 2022, Dynamic Meta-Theorems for Distance and Matching . in M Bojanczyk, E Merelli & D P Woodruff (eds), 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 ., 118, Leibniz International Proceedings in Informatics, LIPIcs, vol. 229, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-20, International Colloquium on Automata, Languages and Programming, Paris, France, 04/07/2022 . https://doi.org/10.4230/LIPIcs.ICALP.2022.118

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202210195992

Collections

[article-cris] Perustieteiden korkeakoulu / SCI

Show all metadata

Dynamic Meta-Theorems for Distance and Matching

Access rights

URL

Journal Title

Journal ISSN

Volume Title

Authors

Date

Department

Major/Subject

Mcode

Degree programme

Language

Pages

Series