Arrow Research search

Author name cluster

Eva Rotenberg

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers
2 author rows

Possible papers

19

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

Details

MFCS Conference 2024 Conference Paper

Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs

  • Ivor van der Hoog
  • André Nusser
  • Eva Rotenberg
  • Frank Staals

A classical problem in computational geometry and graph algorithms is: given a dynamic set 𝒮 of geometric shapes in the plane, efficiently maintain the connectivity of the intersection graph of 𝒮. Previous papers studied the setting where, before the updates, the data structure receives some parameter P. Then, updates could insert and delete disks as long as at all times the disks have a diameter that lies in a fixed range [1/P, 1]. As a consequence of that prerequisite, the aspect ratio ψ (i. e. the ratio between the largest and smallest diameter) of the disks would at all times satisfy ψ ≤ P. The state-of-the-art for storing disks in a dynamic connectivity data structure is a data structure that uses O(Pn) space and that has amortized O(P log⁴ n) expected amortized update time. Connectivity queries between disks are supported in O(log n / log log n) time. In the dynamic setting, one wishes for a more flexible data structure in which disks of any diameter may arrive and leave, independent of their diameter, changing the aspect ratio freely. Ideally, the aspect ratio should merely be part of the analysis. We restrict our attention to axis-aligned squares, and study fully-dynamic square intersection graph connectivity. Our result is fully-adaptive to the aspect ratio, spending time proportional to the current aspect ratio ψ, as opposed to some previously given maximum P. Our focus on squares allows us to simplify and streamline the connectivity pipeline from previous work. When n is the number of squares and ψ is the aspect ratio after insertion (or before deletion), our data structure answers connectivity queries in O(log n / log log n) time. We can update connectivity information in O(ψ log⁴ n + log⁶ n) amortized time. We also improve space usage from O(P ⋅ n log n) to O(n log³ n log ψ) - while generalizing to a fully-adaptive aspect ratio - which yields a space usage that is near-linear in n for any polynomially bounded ψ.

Details

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.

Details

TCS Journal 2022 Journal Article

String indexing for top-k close consecutive occurrences

  • Philip Bille
  • Inge Li Gørtz
  • Max Rishøj Pedersen
  • Eva Rotenberg
  • Teresa Anna Steiner

The classic string indexing problem is to preprocess a string S into a compact data structure that supports efficient subsequent pattern matching queries, that is, given a pattern string P, report all occurrences of P within S. In this paper, we study a basic and natural extension of string indexing called the string indexing for top-k close consecutive occurrences problem (Sitcco). Here, a consecutive occurrence is a pair ( i, j ), i < j, such that P occurs at positions i and j in S and there is no occurrence of P between i and j, and their distance is defined as j − i. Given a pattern P and a parameter k, the goal is to report the top-k consecutive occurrences of P in S of minimal distance. The challenge is to compactly represent S while supporting queries in time close to the length of P and k. We give three time-space trade-offs for the problem. Let n be the length of S, m the length of P, and ϵ ∈ ( 0, 1 ]. Our first result achieves O ( n log ⁡ n ) space and optimal query time of O ( m + k ). Our second and third results achieve linear space and query times either O ( m + k 1 + ϵ ) or O ( m + k log 1 + ϵ ⁡ n ). Along the way, we develop several techniques of independent interest, including a new translation of the problem into a line segment intersection problem and a new recursive clustering technique for trees.

Details DOI

MFCS Conference 2021 Conference Paper

On Dynamic Graphs (Invited Talk)

  • Eva Rotenberg

In graph algorithms, many questions about a graph can be answered in time proportional to the size of the input, and such linear time algorithms are considered the epitome of efficiency. However, when the graph changes slightly, e. g. by the insertion or deletion of an edge or a vertex, it is undesirable to consider the entire input again. Rather, one would wish to keep some of the partial answers to questions about the old graph, and re-use them when computing answers to questions about the resulting graph. The art of handling such changes is studied in dynamic graph algorithms. In this talk, we will see some examples of ideas and techniques for efficiently maintaining knowledge about a dynamically changing graph. We will consider classical and natural graph properties such as connectivity and planarity, and we will focus on deterministic algorithms.

Details

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.

Details

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.

Details

SODA Conference 2018 Conference Paper

A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time

  • Stephen Alstrup
  • Agelos Georgakopoulos
  • Eva Rotenberg
  • Carsten Thomassen

Fleischner's theorem says that the square of every 2-connected graph contains a Hamiltonian cycle. We present a proof resulting in an O (| E |) algorithm for producing a Hamiltonian cycle in the square G 2 of a 2-connected graph G = ( V, E ). The previous best was O (| V | 2 ) by Lau in 1980. More generally, we get an O (| E |) algorithm for producing a Hamiltonian path between any two prescribed vertices, and we get an O (| V | 2 ) algorithm for producing cycles C 3, C 4, …, C | V | in G 2 of lengths 3, 4, …, | V |, respectively.

Details

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.

Details

STOC Conference 2018 Conference Paper

Fast fencing

  • Mikkel Abrahamsen
  • Anna Adamaszek
  • Karl Bringmann
  • Vincent Cohen-Addad
  • Mehran Mehr
  • Eva Rotenberg
  • Alan Roytman
  • Mikkel Thorup

We consider very natural ”fence enclosure” problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set S of n points in the plane, we aim at finding a set of closed curves such that (1) each point is enclosed by a curve and (2) the total length of the curves is minimized. We consider two main variants. In the first variant, we pay a unit cost per curve in addition to the total length of the curves. An equivalent formulation of this version is that we have to enclose n unit disks, paying only the total length of the enclosing curves. In the other variant, we are allowed to use at most k closed curves and pay no cost per curve. For the variant with at most k closed curves,we present an algorithm that is polynomialin both n and k . For the variant with unit cost per curve, or unit disks, we presenta near-linear time algorithm. Capoyleas, Rote, and Woeginger solved the problem with at most k curves in n O ( k ) time. Arkin, Khuller, and Mitchell used this to solve the unit cost per curve version in exponential time. At the time, they conjectured that the problem with k curves is NP-hard for general k . Our polynomial time algorithm refutes this unless P equals NP.

Details

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.

Details

SODA Conference 2018 Conference Paper

The Bane of Low-Dimensionality Clustering

  • Vincent Cohen-Addad
  • Arnaud de Mesmay
  • Eva Rotenberg
  • Alan Roytman

In this paper, we give a conditional lower bound of n Ω( k ) on running time for the classic k -median and k -means clustering objectives (where n is the size of the input), even in low-dimensional Euclidean space of dimension four, assuming the Exponential Time Hypothesis (ETH). We also consider k -median (and k -means) with penalties where each point need not be assigned to a center, in which case it must pay a penalty, and extend our lower bound to at least three-dimensional Euclidean space. This stands in stark contrast to many other geometric problems such as the traveling salesman problem, or computing an independent set of unit spheres. While these problems benefit from the so-called (limited) blessing of dimensionality, as they can be solved in time n O ( k 1-1/ d ) or 2 n 1-1/ d in d dimensions, our work shows that widely-used clustering objectives have a lower bound of n Ω( k ), even in dimension four. We complete the picture by considering the two-dimensional case: we show that there is no algorithm that solves the penalized version in time less than, and provide a matching upper bound of. The main tool we use to establish these lower bounds is the placement of points on the moment curve, which takes its inspiration from constructions of point sets yielding Delaunay complexes of high complexity.

Details

FOCS Conference 2015 Conference Paper

Hashing for Statistics over K-Partitions

  • Søren Dahlgaard
  • Mathias Bæk Tejs Knudsen
  • Eva Rotenberg
  • Mikkel Thorup

In this paper we analyze a hash function for k-partitioning a set into bins, obtaining strong concentration bounds for standard algorithms combining statistics from each bin. This generic method was originally introduced by Flajolet and Martin [FOCS'83] in order to save a factor Ω(k) of time per element over k independent samples when estimating the number of distinct elements in a data stream. It was also used in the widely used Hyper Log Log algorithm of Flajolet et al. [AOFA'97] and in large-scale machine learning by Li et al. [NIPS'12] for minwise estimation of set similarity. The main issue of k-partition, is that the contents of different bins may be highly correlated when using popular hash functions. This means that methods of analyzing the marginal distribution for a single bin do not apply. Here we show that a tabulation based hash function, mixed tabulation, does yield strong concentration bounds on the most popular applications of k-partitioning similar to those we would get using a truly random hash function. The analysis is very involved and implies several new results of independent interest for both simple and double tabulation, e. g. A simple and efficient construction for invertible bloom filters and uniform hashing on a given set.

Details

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

Details
v2026.09.13