Algorithms for Dynamic Graphs

This PhD-dissertation within theoretical computer science studies algorithms, data-structures, and related concepts for dynamic (and static) graphs. It consists of the following parts:

The Power of Multi-step Vizing Chains We show a local version of Vizing’s Theorem,
conjectured by Bonamy, Delcourt, Lang, and Postle [BDLP24]. Then, we show the existence of augmenting supgraphs of size poly (Δ) log n in any proper, partial (Δ+1)-edge-colouring, answering a question of Bernshteyn [Ber22]. This improves the dependency on n from the previous best bound of poly (Δ) log2 n due to Bernshteyn [Ber22], and is tight in the dependency on n due to a lowerbound of Chang, He, Li, Pettie, and Uitto [CHL⁺18]. Using ideas from these two structural theorems, we give an improved LOCAL algorithm for computing (Δ + 1)-edge-colourings, and and a completely explicit dynamic (1 + ε)Δ-edge-colouring algorithm running in poly(log n, ε⁻¹) time.

Deterministic Dynamic Edge-Colouring We give the first sublinear deterministic dynamic edge-colouring algorithm using a number of colours below the greedy threshhold of 2Δ − 1 colours. More specifically, the algorithm runs in n^{olog ε−1 (1)} amortised update time, and uses (1 + ε)Δ colours. Along the way, we give, as far as we can tell, the first sublinear time dynamic degree-splitting algorithm that works against an adaptive adversary.

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity We show that we only need to pack Θ(λ³ logm) greedy trees to guarantee a 1-respecting cut or a trivial cut in some contracted graph. Based on this structural insight, we give a deterministic algorithm for fully dynamic exact min-cut in Õ(λ^5.5√n) worst-case update time for min-cut value bounded by λ. Plugging this algortihm into the framework of Goranci et al. [GHN+23] immediately gives an exact dynamic min-cut algorithm with Õ (m^1−1/12) amortized update time, improving upon the algorithm of Goranci et al. [GHN+23] with update time in Õ(m^1−1/31). We also present the first fully dynamic algorithm that maintains a (1+ε)-approximation of the fractional arboricity α of a dynamic graph G. The algorithm has an amortised update time of O(poly(log m, ε⁻¹)) against an adaptive adversary, and the algorithm works on multigraphs as well.

Adaptive Out-Orientations with Applications We give a naturally adaptive algorithm for (1 + ε)-approximating the maximum subgraph density of a dynamic graph G in worst-case O(ε⁻⁶ log³ n log ρ) update time, thus improving the update time due to Sawlani & Wang [SW20] of O(ε⁻⁶ log⁴ n). The algorithm can also be extended to maintaining a (1+ε)ρ+2-out-orientation of a dynamic graph G in similar update time. We also show how to apply these result to get improved update times for other problems.

Fully Dynamic α + 2 Arboricity Decomp. and Implicit Colouring We give the first dynamic algorithm for maintaining a bounded out-orientation and a dynamic arboricity decomposition with less than 2α out-edges respectively 2α forests, whenever α > 2, in poly(log n, α) update time. More precisely, we show how to maintain an (α + 2)-bounded out-orientation in poly(log n, α) update time and an (α + 2)-arboricity-decomposition in
poly(log n, α) amortised update time.