2026-07-22T04:42:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23421 2025-10-02T12:54:42Z ddc:004 open_access

Online Disjoint Spanning Trees and Polymatroid Bases Chandrasekaran, Karthekeyan Chekuri, Chandra Zhu, Weihao Disjoint Spanning Trees Base Packing Polymatroids Online Algorithms 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 [Schrijver, 2003]. Several other packing problems such as element disjoint Steiner trees, disjoint set covers, and disjoint dominating sets are NP-Hard but admit an O(log n)-approximation [Feige et al., 2002; Cheriyan and Salavatipour, 2007]. Călinescu, Chekuri, and Vondrák [G. Călinescu et al., 2009] 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 [Pananjady et al., 2015; Emek et al., 2019; Bienkowski et al., 2025]. 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 [Quanrud, 2024]. We generalize the previously known result for the online disjoint set cover problem [Emek et al., 2019] 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 poly-logarithmic competitive ratio. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karthekeyan Chandrasekaran and Chandra Chekuri and Weihao Zhu 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.44 urn:nbn:de:0030-drops-234212 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.44 eng https://creativecommons.org/licenses/by/4.0/legalcode