论文标题
距离匹配的游戏，扩展器中的减少APSP以及图形剪切问题的更快的确定性算法
A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems
论文作者
论文摘要
扩展器图在图理论和算法中起着核心作用。随着它们周围开发了许多强大的算法工具，例如剪切匹配游戏，膨胀器修剪，扩展器分解和算法，用于扩展器中的减少全对路径（APSP），仅此而已，在图形算法中使用扩展器的使用已变得泛滥。我们感兴趣的特定应用是静态图中剪切问题的快速确定性算法，以及用于基于动态距离的图形问题（例如APSP）的算法。 不幸的是，在这些设置中使用扩展器会引起许多缺点。例如，在常数扩展程序中使用降低APSP的当前最佳算法只能达到$（\ log n）^{o（1/ε^2）} $ - 与任何$ε$的$ N^{1+O（ε）} $总更新时间的近似。目前在剪切游戏中剪切玩家的所有已知算法都是随机的，或提供相当弱的保证。反过来，这会导致一些中央切割问题的算法保证有些弱：例如，最佳的当前几乎线性时间的确定性算法对于最稀薄的切割算法只能达到近似因子$（\ log n）^{ω（1）} $。最后，当通过当前方法依靠基于距离的问题（例如动态APSP）中的扩展器时，似乎不可避免地必须解决至少$ω（\ log n）$的近似因素。 在本文中，我们建议使用良好的图形，并为此类图引入一种新的算法工具包，从某种意义上说，这些工具包反映了上述扩展器的算法工具。这些新工具之一是距离匹配的游戏，这是与良好连接图的切割匹配游戏的类似物。我们通过为上述几个问题获得更好的结果来证明这些新工具的力量。
Expander graphs play a central role in graph theory and algorithms. With a number of powerful algorithmic tools developed around them, such as the Cut-Matching game, expander pruning, expander decomposition, and algorithms for decremental All-Pairs Shortest Paths (APSP) in expanders, to name just a few, the use of expanders in the design of graph algorithms has become ubiquitous. Specific applications of interest to us are fast deterministic algorithms for cut problems in static graphs, and algorithms for dynamic distance-based graph problems, such as APSP. Unfortunately, the use of expanders in these settings incurs a number of drawbacks. For example, the best currently known algorithm for decremental APSP in constant-degree expanders can only achieve a $(\log n)^{O(1/ε^2)}$-approximation with $n^{1+O(ε)}$ total update time for any $ε$. All currently known algorithms for the Cut Player in the Cut-Matching game are either randomized, or provide rather weak guarantees. This, in turn, leads to somewhat weak algorithmic guarantees for several central cut problems: for example, the best current almost linear time deterministic algorithm for Sparsest Cut can only achieve approximation factor $(\log n)^{ω(1)}$. Lastly, when relying on expanders in distance-based problems, such as dynamic APSP, via current methods, it seems inevitable that one has to settle for approximation factors that are at least $Ω(\log n)$. In this paper we propose the use of well-connected graphs, and introduce a new algorithmic toolkit for such graphs that, in a sense, mirrors the above mentioned algorithmic tools for expanders. One of these new tools is the Distanced Matching game, an analogue of the Cut-Matching game for well-connected graphs. We demonstrate the power of these new tools by obtaining better results for several of the problems mentioned above.
