Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
Yotam Kenneth-Mordoch and Robert Krauthgamer
All-Pairs Minimum Cut (APMC) 是一个基本的图形问题,它要求为每对顶点 s,t 找到一个最小 s,t-cut。 最近针对APMC快速算法的一系列工作最终导致了APMC减少到polylog(n)-许多最大流量计算。 但不幸的是,目前还没有快速算法在几个标准计算模型中以精确的最大流量而闻名,例如剪切模型和全动态模型。 我们的主要技术贡献是一个括约肌,它保留未加权图形中的所有最小 s,t 切口,并且只能使用近似的最大流量计算来构建。 然后,我们使用此ssifier在多个计算模型中的无加权图形中为APMC设计新的算法:(i)一种随机算法,对输入图进行Õ(n^3/2)剪切查询;(ii)具有n^3/2+o(1)最坏情况更新时间的确定性全动态算法;以及(iii)具有空间要求Õ(n^3/2)的随机双通流算法。 这些结果在已知边界上有所改善,即使在相应模型中(单对)最小 s,t-cut。
All-Pairs Minimum Cut (APMC) is a fundamental graph problem that asks to find a minimum s,t-cut for every pair of vertices s,t. A recent line of work on fast algorithms for APMC has culminated with a reduction of APMC to polylog(n)-many max-flow computations. But unfortunately, no fast algorithms are currently known for exact max-flow in several standard models of computation, such as the cut-query model and the fully-dynamic model. Our main technical contribution is a sparsifier that preserves ...
