Fully Dynamic Four-Vertex Subgraph Counting

Kathrin Hanauer, Monika Henzinger, Qi Cheng Hua

Veröffentlichungen: Beitrag in BuchBeitrag in KonferenzbandPeer Reviewed

Abstract

This paper presents a comprehensive study of algorithms for maintaining the number of all connected four-vertex subgraphs in a dynamic graph. Specifically, our algorithms maintain the number of paths 1 of length three in deterministic amortized O(m2) update time, and any other connected four-vertex subgraph which is not a clique in deterministic amortized update time O(m3). Queries can be 2 answered in constant time. We also study the query times for subgraphs containing an arbitrary edge that is supplied only with the query as well as the case where only subgraphs containing a vertex s that is fixed beforehand are considered. For length-3 paths, paws, 4-cycles, and diamonds our bounds match or are not far from (conditional) lower bounds: Based on the OMv conjecture we show that any dynamic algorithm that detects the existence of paws, diamonds, or 4-cycles or that counts length-3 paths takes update time Ω(m 1/ 2−δ). Additionally, for 4-cliques and all connected induced subgraphs, we show a lower bound of Ω(m 1−δ) for any small constant δ > 0 for the amortized update time, assuming the static combinatorial 4-clique conjecture holds. This shows that the O(m) algorithm by Eppstein et al. [9] for these subgraphs cannot be improved by a polynomial factor.

OriginalspracheEnglisch
Titel1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Redakteure*innenJames Aspnes, Othon Michail
ISBN (elektronisch)9783959772242
DOIs
PublikationsstatusVeröffentlicht - 2022
Veranstaltung1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) - Online, USA / Vereinigte Staaten
Dauer: 28 März 202230 März 2022
https://sand-conf.org/
https://sand2022.onrender.com/

Konferenz

Konferenz1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Land/GebietUSA / Vereinigte Staaten
Zeitraum28/03/2230/03/22
Internetadresse

ÖFOS 2012

  • 102031 Theoretische Informatik

Zitationsweisen