Jacob Holm

STOC Conference 2025 Conference Paper

Fully Dynamic Biconnectivity in Õ(log² n) Time

• Jacob Holm
• Wojciech Nadara
• Eva Rotenberg
• Marek Sokolowski 0001

SODA Conference 2024 Conference Paper

Adaptive Out-Orientations with Applications

• Chandra Chekuri
• Aleksander Bjørn Grodt Christiansen
• Jacob Holm
• Ivor van der Hoog
• Kent Quanrud
• Eva Rotenberg
• Chris Schwiegelshohn

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 𝒪 (log 2 n log α), or a worst-case update time of 𝒪 (log 3 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 𝒪 (log 2 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: Firstly, we obtain deterministic algorithms for maintaining a (1 + ɛ) approximation of the maximum subgraph density, ρ, of the dynamic graph. Our algorithms have update times of 𝒪 (ɛ -6 log 3 n log ρ) worst- case, and 𝒪 (ɛ -4 log 2 n log ρ) amortised, respectively. We may output a subgraph H of the input graph where its density is a (1 + ɛ) approximation of the maximum subgraph density in time linear in the size of the subgraph. These algorithms have improved update time compared to the 𝒪 (ɛ -6 log 4 n ) algorithm by Sawlani and Wang from STOC 2020. Secondly, we obtain an 𝒪 (ɛ -6 log 3 n log α) worst-case update time algorithm for maintaining a (1 + ɛ)OPT + 2 approximation of the optimal out-orientation of a graph with adaptive arboricity α, improving the 𝒪(ɛ -6 α 2 log 3 n ) algorithm by Christiansen and Rotenberg from ICALP 2022. This yields the first worst-case polylogarithmic dynamic algorithm for decomposing into 𝒪 (α) forests. Thirdly, we obtain arboricity-adaptive fully-dynamic deterministic algorithms for a variety of problems including maximal matching, Δ + 1 colouring, and matrix vector multiplication. All update times are worst- case 𝒪 (α + log 2 n log α), where α is the current arboricity of the graph. For the maximal matching problem, the state-of-the-art deterministic algorithms by Kopelowitz, Krauthgamer, Porat, and Solomon from ICALP 2014 runs in time 𝒪( α 2 + log 2 n ), and by Neiman and Solomon from STOC 2013 runs in time. We give improved running times whenever the arboricity. * The full version of the paper can be accessed at https: //arxiv. org/abs/2310. 18146

SODA Conference 2023 Conference Paper

Massively Parallel Computation on Embedded Planar Graphs

• Jacob Holm
• Jakub Tetek

Many of the classic graph problems cannot be solved in the Massively Parallel Computation setting (MPC) with strongly sublinear space per machine and o (log n ) rounds, unless the 1-vs-2 cycles conjecture is false. This is true even on planar graphs. Such problems include, for example, counting connected components, bipartition, minimum spanning tree problem, (approximate) shortest paths, and (approximate) diameter/radius. In this paper, we show a way to get around this limitation. Specifically, we show that if we have a “nice” (for example, straight-line) embedding of the input graph, all the mentioned problems can be solved with O ( n 2/3+ε ) space per machine in O (1) rounds. In conjunction with existing algorithms for computing the Delaunay triangulation, our results imply an MPC algorithm for exact Euclidean minimum spanning thee (EMST) that uses O ( n 2/3+ε ) space per machine and finishes in O (1) rounds. This is the first improvement over a straightforward use of the standard Borävka's algorithm with the Dauleanay triangulation algorithm of Goodrich [SODA 1997] which results in Θ(log n ) rounds. This also partially negatively answers a question of Andoni, Nikolov, Onak, and Yaroslavtsev [STOC 2014], asking for lower bounds for exact EMST. We extend our algorithms to work with embeddings consisting of curves that are not “too squiggly” (as formalized by the total absolute curvature). We do this via a new lemma which we believe is of independent interest and could be used to parameterize other geometric problems by the total absolute curvature. We also state several open problems regarding massively parallel computation on planar graphs. * The authors are part of BARC, Basic Algorithms Research Copenhagen, supported by the VILLUM Foundation grant 16582.

MFCS Conference 2022 Conference Paper

On Dynamic α + 1 Arboricity Decomposition and Out-Orientation

• Aleksander Bjørn Grodt Christiansen
• Jacob Holm
• Eva Rotenberg
• Carsten Thomassen

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.

STOC Conference 2020 Conference Paper

Fully-dynamic planarity testing in polylogarithmic time

• Jacob Holm
• Eva Rotenberg

Given a dynamic graph subject to insertions and deletions of edges, a natural question is whether the graph presently admits a planar embedding. We give a deterministic fully-dynamic algorithm for general graphs, running in amortized O (log 3 n ) time per edge insertion or deletion, that maintains a bit indicating whether or not the graph is presently planar. This is an exponential improvement over the previous best algorithm [Eppstein, Galil, Italiano, Spencer, 1996] which spends amortized O (√ n ) time per update.

SODA Conference 2020 Conference Paper

Worst-Case Polylog Incremental SPQR-trees: Embeddings, Planarity, and Triconnectivity

• Jacob Holm
• Eva Rotenberg

We show that every labelled planar graph G can be assigned a canonical embedding φ ( G ), such that for any planar G’ that differs from G by the insertion or deletion of one edge, the number of local changes to the combinatorial embedding needed to get from φ ( G ) to φ ( G’ ) is (log n ). In contrast, there exist embedded graphs where Ω( n ) changes are necessary to accommodate one inserted edge. We provide a matching lower bound of Ω(log n ) local changes, and although our upper bound is worst-case, our lower bound hold in the amortized case as well. Our proof is based on BC trees and SPQR trees, and we develop pre-split variants of these for general graphs, based on a novel biased heavy-path decomposition, where the structural changes corresponding to edge insertions and deletions in the underlying graph consist of at most (log n ) basic operations of a particularly simple form. As a secondary result, we show how to maintain the pre-split trees under edge insertions in the underlying graph deterministically in worst case (log 3 n ) time. Using this, we obtain deterministic data structures for incremental planarity testing, incremental planar embedding, and incremental triconnectivity, that each have worst case (log 3 n ) update and query time, answering an open question by La Poutré and Westbrook from 1998.

FOCS Conference 2019 Conference Paper

Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges

• Jacob Holm
• Valerie King
• Mikkel Thorup
• Or Zamir
• Uri Zwick

Each vertex of an arbitrary simple graph on n vertices chooses k random incident edges. What is the expected number of edges in the original graph that connect different connected components of the sampled subgraph? We prove that the answer is O(n/k), when k ≥ c log n, for some large enough c. We conjecture that the same holds for smaller values of k, possibly for any k ≥ 2. Such a result is best possible for any k ≥ 2. As an application, we use this sampling result to obtain a one-way communication protocol with private randomness for finding a spanning forest of a graph in which each vertex sends only O (√n log n) bits to a referee.

SODA Conference 2018 Conference Paper

Dynamic Bridge-Finding in Õ (log 2 n ) Amortized Time

• Jacob Holm
• Eva Rotenberg
• Mikkel Thorup

We present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in Õ ((log n ) 2 ) amortized time, and can find a bridge in the component of any given vertex, or a bridge separating any two given vertices, in 𝒪 (log n / log log n ) worst case time. Our bounds match the current best for bounds for deterministic fully-dynamic connectivity up to log log n factors. The previous best dynamic bridge finding was an Õ ((log n) 3 ) amortized time algorithm by Thorup [STOC2000], which was a bittrick-based improvement on the 𝒪 ((log n ) 4 ) amortized time algorithm by Holm et al. [STOC98, JACM2001]. Our approach is based on a different and purely combinatorial improvement of the algorithm of Holm et al. , which by itself gives a new combinatorial Õ ((log n ) 3 ) amortized time algorithm. Combining it with Thorup's bittrick, we get down to the claimed Õ ((log n ) 2 ) amortized time. Essentially the same new trick can be applied to the biconnectivity data structure from [STOC98, JACM2001], improving the amortized update time to Õ ((log n ) 3 ). We also offer improvements in space. We describe a general trick which applies to both of our new algorithms, and to the old ones, to get down to linear space, where the previous best use O ( m + n log n log log n ). Our result yields an improved running time for deciding whether a unique perfect matching exists in a static graph.

SODA Conference 2018 Conference Paper

Online Bipartite Matching with Amortized Replacements

• Aaron Bernstein
• Jacob Holm
• Eva Rotenberg

In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω(log n ) lower bound. The previous best strategy known achieved amortized replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014]. For the SAP protocol in particular, nothing better than then trivial bound was known except in special cases. Our analysis immediately implies the same upper bound of reassignments for the capacitated assignment problem, where each vertex on the static side of the bipartition is initialized with the capacity to serve a number of vertices. We also analyze the problem of minimizing the maximum server load. We show that if the final graph has maximum server load L, then the SAP protocol makes amortized reassignments. We also show that this is close to tight because reassignments can be necessary.

FOCS Conference 2015 Conference Paper

Planar Reachability in Linear Space and Constant Time

• Jacob Holm
• Eva Rotenberg
• Mikkel Thorup

We show how to represent a planar digraph in linear space so that reach ability queries can be answered in constant time. The data structure can be constructed in linear time. This representation of reach ability is thus optimal in both time and space, and has optimal construction time. The previous best solution used O(n log n) space for constant query time [Thorup FOCS'01].

SODA Conference 1998 Conference Paper

Direct Routing on Trees (Extended Abstract)

• Stephen Alstrup
• Jacob Holm
• Kristian de Lichtenberg
• Mikkel Thorup

STOC Conference 1998 Conference Paper

Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity

• Jacob Holm
• Kristian de Lichtenberg
• Mikkel Thorup