Online Disjoint Spanning Trees and Polymatroid Bases

Abstract. Finding the maximum number of disjoint spanning trees in a given graph is a well-studied problem with several applications and connections. The Tutte–Nash–Williams theorem provides a min-max relation for this problem which also extends to disjoint bases in a matroid and leads to efficient algorithms [A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003]. Several other packing problems such as element disjoint Steiner trees, disjoint set covers, and disjoint dominating sets are NP-Hard but admit an [Formula: see text]-approximation [U. Feige, M. M. Halldórsson, G. Kortsarz, and A. Srinivasan, SIAM J. Comput., 32 (2002), pp. 172–195], [J. Cheriyan and M. R. Salavatipour, ACM Trans. Algorithms, 3 (2007), 47]. Călinescu, Chekuri, and Vondrák [G. Călinescu, C. Chekuri, and J. Vondrák, Random Structures Algorithms, 35 (2009), pp. 418–430] viewed all these packing problems as packing bases of a polymatroid and provided a unified perspective. Motivated by applications in wireless networks, recent works have studied the problem of packing set covers in the online model [A. Pananjady, V. K. Bagaria, and R. Vaze, The online disjoint set cover problem and its applications, in Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM), 2015, pp. 1221–1229], [Y. Emek, A. Goldbraikh, and E. Kantor, Online disjoint set cover without prior knowledge, in 27th Annual European Symposium on Algorithms (ESA), 2019, 44], [M. Bienkowski, J. Byrka, and Ł. Jeż, Online disjoint set covers: Randomization is not necessary, in 42nd International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, 2025, 18]. The online model poses new challenges for packing problems. In particular, it is not clear how to pack a maximum number of disjoint spanning trees in a graph when edges arrive online. Motivated by these applications and theoretical considerations we formulate an online model for packing bases of a polymatroid, and describe a randomized algorithm with a polylogarithmic competitive ratio. Our algorithm is based on interesting connections to the notion of quotients of a polymatroid that has recently seen applications in polymatroid sparsification [K. Quanrud, Quotient sparsification for submodular functions, in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2024, pp. 5209–5248]. We generalize the previously known result for the online disjoint set cover problem [Y. Emek, A. Goldbraikh, and E. Kantor, Online disjoint set cover without prior knowledge, in 27th Annual European Symposium on Algorithms (ESA), 2019, 44] and also address several other packing problems in a unified fashion. For the special case of packing disjoint spanning trees in a graph (or a hypergraph) whose edges arrive online, we provide an alternative to our general algorithm that is simpler and faster while achieving the same polylogarithmic competitive ratio.