Online Disjoint Spanning Trees and Polymatroid Bases
Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
Source abstract
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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.