摘要
低直径分解（LDD）是设计高效图算法的基本原语。简单来说，LDD是将顶点划分为有界直径聚类的分布，且相邻顶点更可能被聚集在一起。最近，对将LDD的概念扩展到有向图的兴趣日益增长。
在有向图中，有两个自然的对应概念。第一个是有向LDD，删除随机边集后，每个强连通分量的直径较小。第二个是准划分，要求更严格：若一顶点在边删除后仍可到达另一顶点，则这两个顶点在原有向度量中必须接近。每个准划分都会生成一个LDD，但反之则不成立。
本研究开始系统地研究结构化有向图中的LDD。我们的第一个主要结果是，任何具有路径宽度 $\text{pw}$ 的有向图都存在一个 $(O(\text{pw}), \text{Δ})$-LDD。这一结果优于之前隐含自Salmasi等人（SODA'19）准划分结果的 $(2^{O(\text{pw}^2)}, \text{Δ})$-LDD构造。
我们的第二个结果显示，对于一个具有树宽 $\text{tw}$ 的 $n$-顶点图，有向非二分最稀切割 LP松弛的积分间隙为 $O(\text{tw} \log n)$。这优于Mémoli等人（ICALP'16, Algorithmica'18）提出的 $O(\text{tw} \log^2 n)$ 界限。我们通过对Mémoli等人针对有界树宽图的准划分构造的精细分析，得出了这一结果。
博主点评： 本文在有向图的低直径分解方面做出了重要贡献，尤其是提出了新的构造方法并改善了现有的界限。这将对未来有向图算法的设计与分析产生深远影响。