Dynamic Matroids: Base Packing and Covering

Tijn de Vos, ⓡ, Mara Grilnberger · 2025

Read Dynamic Matroids: Base Packing and Covering by Tijn de Vos, ⓡ, Mara Grilnberger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-15460.txt.

Introduction

Tijn de Vos and Mara Grilnberger study matroids that change over time, as elements are added to or removed from the ground set. A matroid is a structure that captures what it means for a set to be independent, a notion behind many optimization problems. Making that structure dynamic could generalize dynamic graph problems such as matching and measures of how densely a graph can be split into trees.

Their core result maintains a base, a largest independent set, as updates arrive. Building on it, they give deterministic algorithms that keep near-exact estimates of base packing and base covering numbers. The update cost stays modest, and one covering algorithm also works with few queries against an opponent who fixes updates in advance.

Catalog record

CREATORTijn de Vos, ⓡ, Mara Grilnberger
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-15460

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dynamic Matroids: Base Packing and Covering Tijn de Vos, ⓡ, Mara Grilnberger 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 ± ε ) (1\pm\varepsilon) -approximation of the base packing number Φ \Phi in O ⁡ ( Φ ⋅ poly ​ ( log ⁡ n , ε − 1 ) ) O(\Phi\cdot\text{poly}(\log n,\varepsilon^{-1})) queries per update. Similarly, we provide a deterministic algorithm that maintains a ( 1 ± ε ) (1\pm\varepsilon) -approximation of the base covering number β \beta in O ⁡ ( β ⋅ poly ​ ( log ⁡ n , ε − 1 ) ) O(\beta\cdot\text{poly}(\log n,\varepsilon^{-1})) queries per update. Moreover, we give an algorithm that maintains a ( 1 ± ε ) (1\pm\varepsilon) -approximation of the base covering number β \beta in O ⁡ ( poly ​ ( log ⁡ n , ε − 1 ) ) O(\text{poly}(\log n,\varepsilon^{-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. Acknowledgements. The authors would like to thank Aleksander Christiansen for the preliminary discussions that were the inspiration for this research. 1 Introduction Matroids generalize different mathematical concepts such as graphs and vector spaces. They have applications in combinatorial optimization, geometry, topology, network theory, and coding theory [ 46 , 30 , 56 , 49 , 23 ] . In particular, matroid problems are often seen as “the problems where greedy algorithms are effective" (see, e.g., [ 50 ] ). Although there are dynamic algorithms for specific matroids, the work on dynamic algorithms for general matroids is limited. Concurrent work by Chandrasekaran, Chekuri, and Zhu [ 7 ] also initiated the somewhat related study of online matroids, where the matroid is slowly revealed over time. With this paper, we would like to develop the study of dynamic matroids by providing efficient algorithms for some fundamental matroid questions. In particular, we study the most basic question of maintaining a base dynamically, providing essential building blocks for future algorithms. Let us start with some definitions. Matroids. Formally, a matroid is defined as a tuple \mathcal{M}=(E,\mathcal{I}) , where E is a finite ground set of elements and \mathcal{I}\subseteq\mathcal{P}(E) a family of independent sets , such that the following three properties hold: 1) Non trivial: \emptyset\in\mathcal{I} . 2) Downward closure: if A\in\mathcal{I} and A^{\prime}\subseteq A , then A^{\prime}\in\mathcal{I} . 3) Exchange property: if A,B\in\mathcal{I} and |A|>|B| , then there is an element e\in A\setminus B such that B\cup\{e\}\in\mathcal{I} . We denote n:=|E| to be the size of the ground set. The rank of a set A\subseteq E is defined as the size of the largest independent set it contains: \rk(A):=\max\limits_{\begin{subarray}{c}A^{\prime}\in\mathcal{I}\text{ s.t.}\\ A^{\prime}\subseteq A\end{subarray}}|A^{\prime}| . We say that B\subseteq E is a base of \mathcal{M} if it is a maximal independent set, i.e., \rk(B)=|B|=\rk(E) . Given a weight function on the elements, a minimum weight base is a base of the smallest total weight. Since \mathcal{I} can be as large as 2^{|E|} , it is often not given explicitly, but implicitly via oracle access. In this paper, we use a rank oracle , which provides \rk(A) upon a query A\subseteq E . Matroid Problems. Two classic matroid problems are matroid union and matroid intersection. They reduce to each other in polynomial time, see, e.g., [ 15 , 40 ] . These problems generalize many graph problems, such as packing disjoint spanning trees, computing the arboricity, bipartite matching, see, e.g., [ 50 ] . Base packing and base covering can be seen as instances of matroid union. In this paper, we investigate these two fundamental cases in the dynamic setting. One well-studied example of a matroid is the graphic matroid , where E is some set of edges and A\subseteq E is independent if and only if it is acyclic. Base packing corresponds to packing disjoint spanning trees and the base covering number corresponds to the arboricity of the graph. Algorithms for base packing and covering have been studied for a long time, see, e.g., [ 39 , 11 , 34 , 35 , 9 , 5 ] . The state of the art is given by Quanrud [ 48 ] . They provide exact algorithms that use \tilde{O}(n+k\cdot\rk(E)^{2}) independence-queries 1 1 1 For simplicity, we use the notation \tilde{O}(f):=O(f\poly\log f) . , where k is the packing/covering number respectively. They also provide (1+\varepsilon) -approximations in \tilde{O}(n/\varepsilon) independence-queries. Dynamic Matroids. For dynamic matroids, we consider element insertions and deletions to the ground set. 2 2 2 The decremental version of this has been studied in [ 4 ] , and we argue below that this fully dynamic version is the natural and most general definition. When an element e is deleted, the independent sets \mathcal{I} simply restrict to the sets without e : \{I\in\mathcal{I}:e\notin I\} . In other words, \mathcal{M} is restricted to E\setminus\{e\} . When an element E is inserted, the adversary also decides on a collection \mathcal{I}_{e} such that (E\cup\{e\},\mathcal{I}\cup\mathcal{I}_{e}) is a matroid and e\in I for every I\in\mathcal{I}_{e} . This means that inserting and then deleting the same element results in the same matroid. The algorithm receives the element updates and can query the (new) independence sets. An alternative definition of dynamic matroids could be as follows. One could allow for updates to \mathcal{I} that do not stem from an element deletion or insertion. However, if we can completely change \mathcal{I} in a single update, then we could go from any matroid on n elements to any other matroid on n elements. This means that any lower bound for a static algorithm carries over to each update of the dynamic algorithm. Hence, recomputing from scratch is the best one could do. On the other extreme, we could only allow adding or deleting a single set I from \mathcal{I} . We note that, in general, such a change to \mathcal{I} will no longer guarantee that it is a matroid: consider adding I to \mathcal{I} . By the downward closure property, all subsets of I also have to be in \mathcal{I} . We consider the most restrictive (and hence most general) version of this, where we only add I if I\setminus\{e\} is already in \mathcal{I} for some element e . The alternative view is that the element e is added to the ground set 3 3 3

Read the complete text