← 研踪 PaperTrailarXiv:2611.10161 · v1
Dynamic Edge Orientation on Low-Arboricity Graphs: Breaking the $\log n$ Barrier
首次提交 2026-11-07 03:32
版本更新 2026-11-07 03:32
雷达观测 2026-11-10 10:11
摘要
We study the dynamic edge orientation problem introduced in a seminal 1999 paper by Brodal and Fagerberg: given a fully dynamic graph with arboricity bounded by , maintain an orientation on 's edges so every vertex has out-degree upper bounded by a function of . They provided an algorithm with amortized update time that maintains an orientation with maximum out-degree . In the decades since, this algorithm has found widespread applications in dynamic graph algorithms. Nevertheless, it has remained a stubborn open question whether, when , the upper bound can be improved. We answer this 27-year-old question in the affirmative, showing that Brodal and Fagerberg's algorithm for maintaining an out-degree orientation runs in amortized update time, which is an exponentially-improved dependence on . This is the first improvement on Brodal and Fagerberg's upper bound even for the case of dynamic forests. Our crucial technical innovation is to construct a hierarchy of dynamic graphs with a property we call near isolation. We believe that this construction may be useful for related problems.
作者备注:29 pages, 3 figures
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-07 03:32 · 最新观测版本
Dynamic Edge Orientation on Low-Arboricity Graphs: Breaking the $\log n$ Barrier
We study the dynamic edge orientation problem introduced in a seminal 1999 paper by Brodal and Fagerberg: given a fully dynamic graph with arboricity bounded by , maintain an orientation on 's edges so every vertex has out-degree upper bounded by a function of . They provided an algorithm with amortized update time that maintains an orientation with maximum out-degree . In the decades since, this algorithm has found widespread applications in dynamic graph algorithms. Nevertheless, it has remained a stubborn open question whether, when , the upper bound can be improved. We answer this 27-year-old question in the affirmative, showing that Brodal and Fagerberg's algorithm for maintaining an out-degree orientation runs in amortized update time, which is an exponentially-improved dependence on . This is the first improvement on Brodal and Fagerberg's upper bound even for the case of dynamic forests. Our crucial technical innovation is to construct a hierarchy of dynamic graphs with a property we call near isolation. We believe that this construction may be useful for related problems.
查看此版本解读 →查看此版本原文 ↗