2025-11-16T20:28:12.488694

Low Recourse Arborescence Forests Under Uniformly Random Arcs

Dahlmeier, Hershkowitz

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 $Î©(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.

academic

Low Recourse Arborescence Forests Under Uniformly Random Arcs

基本信息

论文ID: 2510.02950
标题: Low Recourse Arborescence Forests Under Uniformly Random Arcs
作者: Niklas Dahlmeier (RWTH Aachen), Ellis Hershkowitz (Brown University)
分类: cs.DS (Data Structures and Algorithms), cs.DM (Discrete Mathematics)
发表时间: 2025年10月13日 (arXiv v2)
论文链接: https://arxiv.org/abs/2510.02950

有向树(Arborescence)问题的重要性: 有向树是算法图论中研究最深入的对象之一，自从Chu-Liu/Edmonds算法提出以来，在近线性时间、原对偶、随机化和近似算法等多个领域都有重要应用。
动态算法中的重配置代价: 在动态环境中，目标是在输入随时间变化时维护解。重配置代价(recourse)是衡量动态算法质量的重要指标，表示解决方案随时间的总变化量。低重配置代价算法既降低了更新解的时间复杂度，也提供了本质上更稳定的解。
现有研究的空白: 虽然有向树在静态设置中研究充分，但在动态设置中理解较少。最近Buchbinder等人给出了顶点到达模型的低重配置算法，但对弧到达模型尚无研究。

研究动机

本文的研究动机是填补有向树动态算法的空白，特别是：

扩展现有的顶点到达模型到更一般的弧到达模型
建立与最大二部匹配问题的类比联系
探索随机模型下的可能性边界

核心贡献

建立了对抗性弧到达的不可能性结果: 证明了即使在非自适应对抗模型中，O(n)个弧插入也可能导致Ω(n²)的重配置代价。
提供了随机弧到达的高效算法: 在均匀随机弧到达模型下，给出了期望重配置代价为O(m·log²n)的多项式时间算法。
建立了与最大匹配问题的理论联系: 展示了最大有向树森林问题与最大基数匹配问题在动态设置下的相似性。
开发了新的分析技术: 结合了随机图理论和摊还分析，为类似问题提供了分析框架。

方法详解

任务定义

最大有向树森林问题:

输入：有向图G = (V,A)
输出：有向树森林F ⊆ A，使得F的弧数最大
约束：F的每个弱连通分量都是有向树

增量最大有向树森林问题:

给定顶点集V和弧序列a₁, a₂, ..., aₘ
第i步输出图G⁽ⁱ⁾ := (V, ⋃ⱼ≤ᵢ{aⱼ})的最大有向树森林F⁽ⁱ⁾
目标：最小化重配置代价 ∑ᵢ₌₁ᵐ⁻¹ |F⁽ⁱ⁾ \ F⁽ⁱ⁺¹⁾|

update(F,P) := (F \ ⋃ᵢ parent(vᵢ)) ∪ P

可行路径

定义4 (可行路径): 从根r到根r'的路径P是可行的，如果P = Pₐ ⊕ Pᵥ，其中：

Pₐ的弧包含在r的有向树中
Pᵥ的顶点包含在r'的有向树中

算法1：增量最大有向树森林算法

输入: 顶点集V和弧序列a₁, a₂, ..., aₘ
输出: F⁽¹⁾, F⁽²⁾, ..., F⁽ᵐ⁾

初始化: F⁽⁰⁾ = (V, ∅)
for i = 1 to m:
    if F⁽ⁱ⁻¹⁾在G⁽ⁱ⁾中有可行路径P:
        F⁽ⁱ⁾ ← update(F⁽ⁱ⁻¹⁾, P)
    else:
        F⁽ⁱ⁾ ← F⁽ⁱ⁻¹⁾