DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.57

Dynamic Matroids: Base Packing and Covering

Authors: Tijn de Vos and Mara Grilnberger

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

In this paper, we consider dynamic matroids, where elements can be inserted to or deleted from the ground set over time. The independent sets change to reflect the current ground set. As matroids are central to the study of many combinatorial optimization problems, it is a natural next step to also consider them in a dynamic setting. The study of dynamic matroids has the potential to generalize several dynamic graph problems, including, but not limited to, arboricity and maximum bipartite matching. We contribute by providing efficient algorithms for some fundamental matroid questions. In particular, we study the most basic question of maintaining a base dynamically, providing an essential building block for future algorithms. We further utilize this result and consider the elementary problems of base packing and base covering. We provide a deterministic algorithm that maintains a (1± ε)-approximation of the base packing number Φ in O(Φ ⋅ poly(log n, ε^{-1})) queries per update. Similarly, we provide a deterministic algorithm that maintains a (1± ε)-approximation of the base covering number β in O(β ⋅ poly(log n, ε^{-1})) queries per update. Moreover, we give an algorithm that maintains a (1± ε)-approximation of the base covering number β in O(poly(log n, ε^{-1})) queries per update against an oblivious adversary. These results are obtained by exploring the relationship between base collections, a generalization of tree-packings, and base packing and covering respectively. We provide structural theorems to formalize these connections, and show how they lead to simple dynamic algorithms.

Cite as

Tijn de Vos and Mara Grilnberger. Dynamic Matroids: Base Packing and Covering. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 57:1-57:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{devos_et_al:LIPIcs.ESA.2026.57,
  author =	{de Vos, Tijn and Grilnberger, Mara},
  title =	{{Dynamic Matroids: Base Packing and Covering}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{57:1--57:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.57},
  URN =		{urn:nbn:de:0030-drops-271931},
  doi =		{10.4230/LIPIcs.ESA.2026.57},
  annote =	{Keywords: matroid, minimum weight base, base packing, base covering, dynamic}
}

Document

DOI: 10.4230/LIPIcs.ESA.2026.155

A General Reduction from Near-Additive Emulators to Near-Exact Hopsets

Authors: Julian Aeri, Sebastian Forster, and Mara Grilnberger

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

Graph emulators and hopsets are two fundamental concepts for distance approximation. For a given graph G, an (α,β)-emulator is a sparse graph on the same vertex set that preserves the distances of G up to a multiplicative stretch α and additive stretch β. In contrast, an (α,β)-hopset is a set of additional edges that, when added to G, ensures that distances can be approximated up to a multiplicative stretch α, using paths containing at most β edges. When α = 1+ε for arbitrarily small ε > 0, these structures are known as near-additive emulators and near-exact hopsets, respectively. Prior work showed that there is a remarkable similarity between the constructions and guarantees of these two objects. In their survey on this topic, Elkin and Neiman [Bull. EATCS 130, 2020] explicitly asked whether one can obtain a general reduction between near-additive emulators and near-exact hopsets. Following that, Kogan and Parter [FOCS, 2022] provided a general reduction from hopsets to emulators and spanners. In this paper, we address the reverse direction and show that any construction for a near-additive emulator for undirected unweighted graphs can be leveraged as a black box to construct a hopset for an undirected weighted graph with comparable size, stretch, and a hopbound comparable to the emulator’s additive stretch. Specifically, we show that any algorithm that constructs a (1+ε',β)-emulator, with 0 ≤ ε' ≤ 1 and β ≥ 1, of size S_𝒜(n, ε',β), can be used to obtain a (1+ε, O(β²/ε² ln(n/ε)))-hopset of size O((S_𝒜(n + m β/ε², ε/294, β) 1/ε + n) ln(n/ε)), for any 0 < ε ≤ 1. Therefore, our reduction answers the question of Elkin and Neiman [Bull. EATCS 130, 2020] for sparse graphs and further advances the understanding of the formal connection between these two structures. Designing a reduction resulting in a hopset size that does not depend on m remains an intriguing open question.

Cite as

Julian Aeri, Sebastian Forster, and Mara Grilnberger. A General Reduction from Near-Additive Emulators to Near-Exact Hopsets. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 155:1-155:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aeri_et_al:LIPIcs.ESA.2026.155,
  author =	{Aeri, Julian and Forster, Sebastian and Grilnberger, Mara},
  title =	{{A General Reduction from Near-Additive Emulators to Near-Exact Hopsets}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{155:1--155:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.155},
  URN =		{urn:nbn:de:0030-drops-272919},
  doi =		{10.4230/LIPIcs.ESA.2026.155},
  annote =	{Keywords: hopsets, shortest paths, emulator-to-hopset-reduction}
}

Search Results

Documents authored by Grilnberger, Mara

Dynamic Matroids: Base Packing and Covering

Abstract

Cite as

A General Reduction from Near-Additive Emulators to Near-Exact Hopsets

Abstract

Cite as

Thanks for your feedback!

Could not send message