Low Recourse Arborescence Forests Under Uniformly Random Arcs

Abstract

In this work, we study how to maintain a forest of arborescences of maximum arc cardinality under arc insertions while minimizing recourse -- the total number of arcs changed in the maintained solution. This problem is the "arborescence version'' of max cardinality matching. On the impossibility side, we observe that even in this insertion-only model, it is possible for $m$ adversarial arc arrivals to necessarily incur $\hat{I}\text{c◯}(m\cdot n)$ recourse, matching a trivial upper bound of $O(m\cdot n)$. On the possibility side, we give an algorithm with expected recourse $O(m\cdot {\log }^{2}n)$ if all $m$ arcs arrive uniformly at random.

21 pages (22 including title page), 4 figures