Given a dynamic graph \(G\) with \(n\) vertices and \(m\) edges subject to insertions and deletions of edges, we show how to maintain a \((1+\varepsilon)\Delta\)-edge-colouring of \(G\) without the use of randomisation. More specifically, we show a deterministic dynamic algorithm with an amortised update time of \(2^{\tilde{O}_{\log \varepsilon^{-1}}(\sqrt{\log n})}\) using \((1+\varepsilon)\Delta\) colours. If \(\varepsilon^{-1} \in 2^{O(\log^{0.49} n)}\), then our update time is sub-polynomial in \(n\).

Abstract Tree-packings – collections of spanning trees of a graph – are a fundamental tool in the study of minimum cut and related graph parameters. They have played a central role in the design of algorithms across static, dynamic, and distributed settings. In this paper, we study both tree-packings themselves and their structural connections to min-cut and arboricity. Our results lead to faster dynamic algorithms for both problems. For dynamic min-cut, [Thorup, Comb. 2007] used tree-packings to obtain his dynamic min-cut algorithm with $$\tilde{O}(\lambda ^{14.5}\sqrt{n})$$ O ~ ( λ 14.5 n ) worst-case update time. We reexamine this relationship, showing that we need to maintain fewer trees for such a result; we show that we only need to pack $$\Theta (\lambda ^3 \log m)$$ Θ ( λ 3 log m ) greedy trees to guarantee either a 1-respecting cut or a trivial cut in some contracted graph. Based on this structural result, we then provide a deterministic algorithm for fully dynamic exact min-cut that has $$\tilde{O}(\lambda ^{5.5}\sqrt{n})$$ O ~ ( λ 5.5 n ) worst-case update time, for graphs with min-cut value at most $$\lambda $$ λ . In particular, this also yields an algorithm for fully dynamic exact min-cut with $$\tilde{O}(m^{1-1/12})$$ O ~ ( m 1 - 1 / 12 ) amortized update time, improving upon $$\tilde{O}(m^{1-1/31})$$ O ~ ( m 1 - 1 / 31 ) [Goranci et al., SODA 2023]. We also give the first fully dynamic algorithm that maintains a $$(1+\varepsilon )$$ ( 1 + ε ) -approximation of the fractional arboricity. Our algorithm is deterministic and has $$O(\alpha \log ^6m/\varepsilon ^4)$$ O ( α log 6 m / ε 4 ) amortized update time, for graphs with arboricity at most $$\alpha $$ α

A tree-packing is a collection of spanning trees of a graph. It has been a useful tool for computing the minimum cut in static, dynamic, and distributed settings. In particular, [Thorup, Comb. 2007] used them to obtain his dynamic min-cut algorithm with worst-case update time. We reexamine this relationship, showing that we need to maintain fewer spanning trees for such a result; we show that we only need to pack Θ(λ3 log m ) greedy trees to guarantee a 1-respecting cut or a trivial cut in some contracted graph. Based on this structural result, we then provide a deterministic algorithm for fully dynamic exact min-cut, that has worst-case update time, for min-cut value bounded by λ. In particular, this also leads to an algorithm for general fully dynamic exact min-cut with amortized update time, improving upon Õ (m 1-1/31 ) [Goranci et al., SODA 2023]. We also give the first fully dynamic algorithm that maintains a (1 + ε )-approximation of the fractional arboricity - which is strictly harder than the integral arboricity. Our algorithm is deterministic and has O (α log6 m/ε 4) amortized update time, for arboricity at most a. We extend these results to a Monte Carlo algorithm with O (poly(log m, ε -1)) amortized update time against an adaptive adversary. Our algorithms work on multi-graphs as well. Both result are obtained by exploring the connection between the min-cut/arboricity and (greedy) tree-packing. We investigate tree-packing in a broader sense; including a lower bound for greedy treepacking, which – to the best of our knowledge – is the first progress on this topic since [Thorup, Comb. 2007].

The densest subgraph problem is a classic problem in combinatorial optimisation. Graphs with low maximum subgraph density are often called "uniformly sparse", leading to algorithms parameterised by this density. However, in reality, the sparsity of a graph is not necessarily uniform. This calls for a formally well-defined, fine-grained notion of density. Danisch, Chan, and Sozio propose a definition for local density that assigns to each vertex v a value ρ^*(v). This local density is a generalisation of the maximum subgraph density of a graph. I.e., if ρ(G) is the subgraph density of a finite graph G, then ρ(G) equals the maximum local density ρ^*(v) over vertices v in G. They present a Frank-Wolfe-based algorithm to approximate the local density of each vertex with no theoretical (asymptotic) guarantees. We provide an extensive study of this local density measure. Just as with (global) maximum subgraph density, we show that there is a dual relation between the local out-degrees and the minimum out-degree orientations of the graph. We introduce the definition of the local out-degree g^*(v) of a vertex v, and show it to be equal to the local density ρ^*(v). We consider the local out-degree to be conceptually simpler, shorter to define, and easier to compute. Using the local out-degree we show a previously unknown fact: that existing algorithms already dynamically approximate the local density for each vertex with polylogarithmic update time. Next, we provide the first distributed algorithms that compute the local density with provable guarantees: given any ε such that ε^{-1} ∈ O(poly n), we show a deterministic distributed algorithm in the LOCAL model where, after O(ε^{-2} log² n) rounds, every vertex v outputs a (1 + ε)-approximation of their local density ρ^*(v). In CONGEST, we show a deterministic distributed algorithm that requires poly(log n,ε^{-1}) ⋅ 2^{O(√{log n})} rounds, which is sublinear in n. As a corollary, we obtain the first deterministic algorithm running in a sublinear number of rounds for (1+ε)-approximate densest subgraph detection in the CONGEST model.

We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the maximum out-degree is bounded. On one hand, we show how to orient the edges such that maximum out- degree is proportional to the arboricity α of the graph, in, either, an amortised update time of 𝒪(log2 n log α), or a worst-case update time of 𝒪 (log3 n log α). On the other hand, motivated by applications including dynamic maximal matching, we obtain a different trade-off. Namely, the improved update time of either 𝒪 (log n log α), amortised, or 𝒪(log2 n log α), worst-case, for the problem of maintaining an edge-orientation with at most 𝒪 (α + log n) out-edges per vertex. Finally, all of our algorithms naturally limit the recourse to be polylogarithmic in n and α. Our algorithms adapt to the current arboricity of the graph, and yield improvements over previous work:

We show that every planar triangulation on n > 10 vertices has a dominating set of size 2n/7 = n/3.5. This approaches the n/4 bound conjectured by Matheson and Tarjan [12], and improves significantly on the previous best bound of 17n/53 ≈ n/3.117 by Spacapan [18].

Given a dynamic graph subject to edge insertions and deletions, we show how to update an implicit representation of a proper vertex colouring, such that colours of vertices are computable upon query time. We give a deterministic algorithm that uses O(α 2) colours for a dynamic graph of arboricity α, and a randomised algorithm that uses O(min{α logα, α logloglogn}) colours in the oblivious adversary model. Our deterministic algorithm has update- and query times polynomial in α and logn, and our randomised algorithm has amortised update- and query time that with high probability is polynomial in logn with no dependency on the arboricity.

Recent papers have addressed different variants of the (Δ + 1)-edge-colouring problem by concatenating or gluing together many Vizing chains to form what Bernshteyn coined multi-step Vizing chains. In this paper, we consider the most general definition of this term and apply different multi-step Vizing chain constructions to prove combinatorial properties of edge-colourings that lead to (improved) algorithms for computing edge-colouring across different models of computation. This approach seems especially powerful for constructing augmenting subgraphs which respect some notion of locality.

In the implicit dynamic colouring problem, the task is to maintain a representation of a proper colouring as a dynamic graph is subject to insertions and deletions of edges, while facilitating interspersed queries to the colours of vertices. The goal is to use few colours, while still efficiently handling edge-updates and responding to colour-queries. For an n-vertex dynamic graph of arboricity $α$, we present an algorithm that maintains an implicit vertex colouring with $4\cdot2^α$ colours, in amortised poly-$(\log n)$ update time, and with $O(α log n)$ worst-case query time. The previous best implicit dynamic colouring algorithm uses $2^{40α}$) colours, and has a more efficient update time of $O(\log^3 n)$ and the same query time of $O(α log n)$ [Henzinger et al'20]. For graphs undergoing arboricity $α$ preserving updates, we give a fully-dynamic $α+2$ arboricity decomposition in poly$(\log n,α)$ time, which matches the number of forests in the best near-linear static algorithm by Blumenstock and Fischer [2020] who obtain $α+2$ forests in near-linear time. Our construction goes via dynamic bounded out-degree orientations, where we present a fully-dynamic explicit, deterministic, worst-case algorithm for $\lfloor (1+\varepsilon)α\rfloor + 2$ bounded out-degree orientation with update time $O(\varepsilon^{-6}α^2 \log^3 n)$. The state-of-the-art explicit, deterministic, worst-case algorithm for bounded out-degree orientations maintains a $β\cdot α+ \log_β n$ out-orientation in $O(β^2α^2+βα\log_β n)$ time [Kopelowitz et al'13].

A graph has arboricity α if its edges can be partitioned into α forests. The dynamic arboricity decomposition problem is to update a partitioning of the graph’s edges into forests, as a graph undergoes insertions and deletions of edges. We present an algorithm for maintaining partitioning into α+1 forests, provided the arboricity of the dynamic graph never exceeds α. Our algorithm has an update time of Õ(n^{3/4}) when α is at most polylogarithmic in n. Similarly, the dynamic bounded out-orientation problem is to orient the edges of the graph such that the out-degree of each vertex is at all times bounded. For this problem, we give an algorithm that orients the edges such that the out-degree is at all times bounded by α+1, with an update time of Õ(n^{5/7}), when α is at most polylogarithmic in n. Here, the choice of α+1 should be viewed in the light of the well-known lower bound by Brodal and Fagerberg which establishes that, for general graphs, maintaining only α out-edges would require linear update time. However, the lower bound by Brodal and Fagerberg is non-planar. In this paper, we give a lower bound showing that even for planar graphs, linear update time is needed in order to maintain an explicit three-out-orientation. For planar graphs, we show that the dynamic four forest decomposition and four-out-orientations, can be updated in Õ(n^{1/2}) time.