论文标题
扩展器层次结构及其在动态图算法中的应用
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
论文作者
论文摘要
我们介绍了一个用于层次图聚类的概念，我们称之为扩展器层次结构，并显示了一种完全动态的算法，用于在图形上维护这样的层次结构，其中$ n $ dertices使用$ n^{o（o（1）$更新时间）。扩展器层次结构是图表的树表示，忠实地捕获了切割结构，因此我们的动态算法几乎立即暗示了几个结果，包括： (1) The first fully dynamic algorithm with $n^{o(1)}$ worst-case update time that allows querying $n^{o(1)}$-approximate conductance, $s$-$t$ maximum flows, and $s$-$t$ minimum cuts for any given $(s,t)$ in $O(\log^{1/6} n)$ time.我们的结果是确定性的，并扩展到多商品削减和流动。这些结果背后的关键思想是一种完全动态的算法，用于维护树流稀疏器，这是Räcke[focs'02]介绍的概念，用于构建竞争性的遗忘路由方案。 （2）具有$ n^{o（1）} $最差的更新时间的确定性完全动态连接算法。这大大简化了Chuzhoy等人的最新算法，该算法使用Nanongkai等人的框架。 [焦点17]。 （3）第一个非平凡的确定性完全动态的完全动态的树宽分解算法在恒定的图表上，带有$ n^{o（1）} $最差的更新时间，该更新时间保持宽度的宽度$ \ text {tw}（g）（g）\ cdot n^$ n $ n $ n $ n $ n $ de twide twide witth $ \ text $（当前图。 我们的技术是基于扩展器分解的新概念，称为边界链接扩展器分解。这种分解比更新更强大，并更好地捕获了图的聚类结构。鉴于膨胀剂的分解在许多领域都非常有用，我们希望我们的新概念会发现更多未来的应用程序。
We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with $n$ vertices undergoing edge insertions and deletions using $n^{o(1)}$ update time. An expander hierarchy is a tree representation of graphs that faithfully captures the cut-flow structure and consequently our dynamic algorithm almost immediately implies several results including: (1) The first fully dynamic algorithm with $n^{o(1)}$ worst-case update time that allows querying $n^{o(1)}$-approximate conductance, $s$-$t$ maximum flows, and $s$-$t$ minimum cuts for any given $(s,t)$ in $O(\log^{1/6} n)$ time. Our results are deterministic and extend to multi-commodity cuts and flows. The key idea behind these results is a fully dynamic algorithm for maintaining a tree flow sparsifier, a notion introduced by Räcke [FOCS'02] for constructing competitive oblivious routing schemes. (2) A deterministic fully dynamic connectivity algorithm with $n^{o(1)}$ worst-case update time. This significantly simplifies the recent algorithm by Chuzhoy et al.~that uses the framework of Nanongkai et al. [FOCS'17]. (3) The first non-trivial deterministic fully dynamic treewidth decomposition algorithm on constant-degree graphs with $n^{o(1)}$ worst-case update time that maintains a treewidth decomposition of width $\text{tw}(G)\cdot n^{o(1)}$ where $\text{tw}(G)$ denotes the treewidth of the current graph. Our technique is based on a new stronger notion of the expander decomposition, called the boundary-linked expander decomposition. This decomposition is more robust against updates and better captures the clustering structure of graphs. Given that the expander decomposition has proved extremely useful in many fields, we expect that our new notion will find more future applications.
