Dynamic Meta-Theorems for Distance and Matching

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

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

44 Lataukset (Pure)

Abstrakti

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].

AlkuperäiskieliEnglanti
Otsikko49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
ToimittajatMikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivut1-20
Sivumäärä20
ISBN (elektroninen)978-3-95977-235-8
DOI - pysyväislinkit
TilaJulkaistu - 1 heinäk. 2022
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaInternational Colloquium on Automata, Languages and Programming - Paris, Ranska
Kesto: 4 heinäk. 20228 heinäk. 2022
Konferenssinumero: 49
https://icalp2022.irif.fr/

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
KustantajaSchloss Dagstuhl-Leibniz-Zentrum für Informatik
Vuosikerta229
ISSN (elektroninen)1868-8969

Conference

ConferenceInternational Colloquium on Automata, Languages and Programming
LyhennettäICALP
Maa/AlueRanska
KaupunkiParis
Ajanjakso04/07/202208/07/2022
www-osoite

Sormenjälki

Sukella tutkimusaiheisiin 'Dynamic Meta-Theorems for Distance and Matching'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä