最小割

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 什么是割

一个割把图的顶点分成两个非空的组： S 和其余部分 V \ S。两端分别位于两组中的边跨越这个割，删除这些边就会使两组彼此断开。在带权图中，割的权重，也称为它的容量，是跨越边的权重总和；在无权图中，它就是这些边的条数。最小割是权重最小的割：把图拆成两部分的最便宜的方式。

贯穿全文的示例是一个由 15 条链路连接 8 台路由器的小型计算机网络。每个权重是一条链路的容量，单位为 Gbit/s。路由器 A 到 D 位于一栋楼中， E 到 H 位于另一栋楼中：

1 号楼:      A-B 4   A-C 3   A-D 2   B-C 2   B-D 3   C-D 3
2 号楼:      E-F 3   E-G 2   E-H 3   F-G 4   F-H 2   G-H 3
两楼之间:    C-E 2   D-F 1   B-G 1

8 台路由器，15 条链路，总容量 38

切断两楼之间的三条链路 C-E、 D-F 和 B-G，代价为 2 + 1 + 1 = 4，并把网络分成两部分。这就是最小割，而且它是唯一一个权重为 4 的割。它也是网络的最薄弱之处：无论网络的其余部分如何配置，两栋楼之间最多只能交换 4 Gbit/s 的流量。次便宜的割孤立路由器 H，代价为 8，即它自身各条链路的权重之和。

2. 同名的两个问题

“最小割”指的是两个相关的问题，关于这一主题的大多数困惑都来自把它们混为一谈：

• 最小 s-t 割。给定两个顶点，即源点 s 和汇点 t，割必须把它们分开： s 在 S中， t 在其外。这就是第 4 节最大流最小割定理中的割。在示例中，把 A 与 H 分开的最小割是权重为 4 的楼间割，但把 A 与 B 分开的最小割权重为 9：由于两者在同一栋楼里，最便宜的做法是把 A 单独切出来。
• 全局最小割。不给定任何顶点；割可以分开任意两个组。它的权重是所有 s-t 最小割中最小的那个，在无权图中，它等于边连通度 λ(G)，即使图不连通所需删除的最少边数。第 5 至 7 节计算它。

一个简单的界把这两个概念联系起来。切出单个顶点的代价是它的各条链路权重之和，即它的带权度，所以全局最小割永远不会超过最小的度。Hassler Whitney 在 1932 年证明了无权的版本：点连通度 ≤ 边连通度 ≤ 最小度。在示例中，最小的带权度为 8，出现在 H处，而 4 的最小割远低于它：薄弱之处是两组之间的一束链路，而不是某一台连接很差的路由器。如果不考虑权重，这个界在这里是紧的：每台路由器至少有 3 条链路，而 3 条链路正是使网络断开所需的最少数目。

3. 为什么逐一尝试所有割行不通

一个有 n 个顶点的图有 2n-1 - 1 个割：除了固定的第一个顶点之外，每个顶点都可以放到任一侧，而所有顶点都在同一侧的划分不是割。示例有 27 - 1 = 127个割，少到可以逐一列出。

from itertools import combinations

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def cut_weight(side, links):
    """恰好有一个端点在 side 中的链路的总权重。"""
    return sum(w for u, v, w in links if (u in side) != (v in side))

def all_cuts(links):
    """把顶点分成两个非空侧的每一种划分，每种只计一次。"""
    vertices = sorted({x for u, v, _ in links for x in (u, v)})
    first, rest = vertices[0], vertices[1:]
    for r in range(len(rest)):                 # side 总是包含第一个顶点
        for others in combinations(rest, r):
            side = {first, *others}
            yield cut_weight(side, links), ''.join(sorted(side))

cuts = sorted(all_cuts(LINKS))
print(len(cuts), 'cuts')
# 127 cuts
for weight, side in cuts[:4]:
    print(weight, side)
# 4 ABCD
# 8 ABCDEFG
# 9 A
# 9 ABCEFGH

每增加一个顶点，割的数目就翻一倍：50 个顶点就已经给出超过 560 万亿个割。本指南的其余部分讨论的是无需查看其中大部分割就能找到最小割的算法。关于图算法复杂度的指南解释了为什么这样的指数增长排除了暴力穷举。

4. 由最大流求最小 s-t 割

根据最大流最小割定理（由 Lester Ford 和 Delbert Fulkerson 于 1954 年在一份 RAND 报告中提出，1956 年发表；同一年，Peter Elias、Amiel Feinstein 和 Claude Shannon 给出了另一种证明），从 s 到 t 所能发送的最大流量等于把它们分开的最小割的权重。一个方向很容易：每一单位的流都必须穿过每一个 s-t 割，所以任何流都不能超过任何割。这个定理的实质在于两者总是相等。关于网络流与最大流最小割定理的指南用增广路径证明了它。

这个问题起源于军事。1955 年，RAND Corporation 的 T. E. Harris 和 F. S. Ross 把苏联西部和东欧的铁路建模为一个有 44 个顶点和 105 条边的网络，以找出破坏代价最小的一组线路。他们对割比对流更感兴趣：他们的报告把一个 163,000 吨的最小割标为“瓶颈”。这份报告直到 1999 年才解密。

对于计算割而言，重要的是割如何从最大流中得出。当不再有从 s 到 t 的增广路径时，收集 s 通过有剩余容量的边，也就是残量网络，仍能到达的每个顶点。这个集合就是最小割的 S 一侧，而离开它的满载边就是割。下面的程序运行 Edmonds-Karp 算法（它总是沿最短路径增广），然后读出割。每条无向链路都可以在任一方向上承载流。

from collections import deque

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def min_st_cut(links, s, t):
    """Edmonds-Karp 最大流，然后从残量网络中读出最小 s-t 割。"""
    cap = {}
    for u, v, w in links:                      # 无向链路可以在任一方向上承载流
        cap.setdefault(u, {})[v] = cap.get(u, {}).get(v, 0) + w
        cap.setdefault(v, {})[u] = cap.get(v, {}).get(u, 0) + w
    flow = 0
    while True:
        parent, queue = {s: None}, deque([s])
        while queue and t not in parent:       # 用 BFS 求最短增广路径
            u = queue.popleft()
            for v, c in cap[u].items():
                if c > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)
        if t not in parent:
            break
        path, v = [], t
        while parent[v] is not None:
            path.append((parent[v], v))
            v = parent[v]
        push = min(cap[u][v] for u, v in path)
        for u, v in path:                      # 用掉容量，打开反方向
            cap[u][v] -= push
            cap[v][u] += push
        flow += push
    side = set(parent)                         # 在残量网络中仍可从 s 到达
    cut = [(u, v, w) for u, v, w in links if (u in side) != (v in side)]
    return flow, ''.join(sorted(side)), cut

print(min_st_cut(LINKS, 'A', 'H'))
# (4, 'ABCD', [('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)])
print(min_st_cut(LINKS, 'A', 'B'))
# (9, 'A', [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2)])

从 A 到 H，最大流为 4，它可以拆分成分别承载 2、1 和 1 个单位的三条路径。此后，两楼之间的三条链路都已满载， A 仍能到达 B、 C 和 D，但无法到达更远处，割恰好就是楼间割。从 A 到 B，流为 9，割把 A单独孤立出来。Edmonds-Karp 的运行时间为 O(V E2)；存在更快的流算法，但任何正确的流算法都能以这种方式给出最小 s-t 割。

对于无权图，这个定理有一个著名的组合形式，通常以 Karl Menger 的名字命名，他在 1927 年的定理是关于顶点的版本：从 u 到 v、彼此没有公共边的路径的最大条数，等于把 u 与 v分开所需删除的最少边数。这种边形式的 Menger 定理可以由最大流最小割定理推出。在示例中，不考虑权重时，从 A 到 H有三条边不相交的路径，而两楼之间也有三条链路。

5. 用最大流求全局最小割

全局最小割分开的是某一对顶点，因此它是所有顶点对上最小的 s-t 割。其实用不着那么多对。固定任意一个顶点 s：无论最小割是什么，总有某个顶点 t 位于它的另一侧，所以对 n - 1 种 t 的选择取最小值，就能找到它。在示例中，固定 s = A后， t 位于另一栋楼中的四次运行全都返回 4。

Ralph Gomory 和 T. C. Hu 在 1961 年证明， n - 1 次最大流计算能揭示更多信息：它们在同样的顶点上构建一棵树，现在称为 Gomory-Hu 树，其中任意两个顶点之间的最小割等于连接它们的树上路径中最小的边权。对于示例，这棵树的七条边的值分别为 4、8、9、9、10、10 和 10，因此 28 个两两最小割中每一个的值都可以从树上读出，而最小的边 4 就是全局最小割。

基于流的方法也适用于有向图，当特定顶点之间的最小割很重要时，它们是合适的工具。对于无向图的全局最小割，接下来的两种算法更简单，也更快。

6. Stoer-Wagner 算法

1997 年，Mechthild Stoer 和 Frank Wagner 在 Hiroshi Nagamochi 和 Toshihide Ibaraki 早期工作的基础上，发表了一种完全不用流就能求出非负权无向图全局最小割的算法。它分 n - 1 个阶段进行。每个阶段做三件事：

1. 从任意一个顶点开始，每次加入一个顶点，总是选择与已加入顶点连接最紧密的那个：即连向这个不断增长的集合的链路总权重最大的顶点。这种顺序称为最大邻接搜索。
2. 当最后一个顶点 t 被加入时，它连向其余所有顶点的链路权重就是阶段割。一个简短的论证表明，它是把 t 与紧挨在它之前加入的顶点 s分开的最小割。
3. 把 s 和 t 合并为一个顶点，把平行链路的权重相加，然后在更小的图上开始下一个阶段。

全局最小割要么把 s 与 t分开，这时这个阶段已经找到了它；要么把它们留在同一侧，这时合并它们不会损失任何东西。经过 n - 1 个阶段后，最小的阶段割就是答案。

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def stoer_wagner(links):
    """全局最小割：n - 1 个阶段，每个阶段以一个阶段割和一次合并结束。"""
    w = {}
    for u, v, c in links:
        w.setdefault(u, {})[v] = w.get(u, {}).get(v, 0) + c
        w.setdefault(v, {})[u] = w.get(v, {}).get(u, 0) + c
    groups = {v: v for v in w}                 # 合并后的顶点记住自己包含哪些顶点
    best, phase = (float('inf'), ''), 0
    while len(w) > 1:
        phase += 1
        start = min(w)
        order, attached = [start], {v: w[start].get(v, 0) for v in w if v != start}
        while attached:                        # 下一个加入连接最紧密的顶点
            v = max(sorted(attached), key=attached.get)
            phase_cut = attached.pop(v)
            order.append(v)
            for x, c in w[v].items():
                if x in attached:
                    attached[x] += c
        s, t = order[-2], order[-1]
        side = ''.join(sorted(groups[t]))
        print(f'phase {phase}: cut of the phase {phase_cut:2}, side {side}')
        best = min(best, (phase_cut, side))
        for x, c in w.pop(t).items():          # 把 t 合并到 s 中
            if x != s:
                w[s][x] = w[s].get(x, 0) + c
                w[x][s] = w[x].get(s, 0) + c
            del w[x][t]
        groups[s] += groups.pop(t)
    return best

print(stoer_wagner(LINKS))
# phase 1: cut of the phase  8, side H
# phase 2: cut of the phase 10, side F
# phase 3: cut of the phase 10, side FGH
# phase 4: cut of the phase  4, side EFGH
# phase 5: cut of the phase 10, side C
# phase 6: cut of the phase 10, side B
# phase 7: cut of the phase  9, side BCDEFGH
# (4, 'EFGH')

在示例中，第一个阶段在 H 处结束，割为 8，即孤立它的代价。随着各阶段不断合并顶点，组会越来越大：到第 4 阶段，最后加入的顶点是合并后的组 E, F, G, H，它的阶段割就是楼间割 4。其余阶段只能找到更大的割。用 Fibonacci 堆来实现“连接最紧密”的选择时，每个阶段需要 O(E + V log V)，整个算法需要 O(V E + V2 log V)；上面这个通过扫描找最大值的简单版本需要 O(V3)。

7. Karger 随机收缩

David Karger 于 1993 年提出的算法是最著名的随机算法之一。它简单得让人几乎不相信它能行得通：

1. 随机选取一条链路，选中的概率与其权重成正比，然后收缩它：把它的两个端点合并为一个顶点，并丢弃两者之间的链路。
2. 重复这一过程，直到只剩下两个合并后的顶点。
3. 这两个顶点之间的链路构成一个割。报告这个割。

单次运行很容易失败：只要它在某一步收缩了最小割中的一条链路，这个割就丢失了。令人惊讶的是，它失败的次数足够少。最小割很轻，所以随机选择往往会避开它的链路，Karger 证明了单次运行返回某个给定最小割的概率至少为 2 / (n (n - 1))。重复运行并保留最轻的割，就能让失败概率按你希望的速度下降。

import math, random

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def contract(links, rnd):
    """Karger 算法的一次运行：合并随机链路的两端，直到只剩两个组。"""
    group = {x: x for u, v, _ in links for x in (u, v)}
    def find(x):
        while group[x] != x:
            x = group[x]
        return x
    groups = len(group)
    while groups > 2:
        alive = [(u, v, w) for u, v, w in links if find(u) != find(v)]
        u, v, _ = rnd.choices(alive, weights=[w for *_, w in alive])[0]   # 越重的链路越常被合并
        group[find(u)] = find(v)
        groups -= 1
    side = ''.join(sorted(x for x in group if find(x) == find('A')))
    return sum(w for u, v, w in links if find(u) != find(v)), side

rnd = random.Random(2026)
runs = [contract(LINKS, rnd) for _ in range(10_000)]
hits = sum(weight == 4 for weight, _ in runs)
print(f'minimum cut found in {hits} of 10,000 runs')
print(f'guaranteed at least 2 / (n (n - 1)) = {2 / (8 * 7):.4f} per run')
best_of_10 = [min(runs[i:i + 10]) for i in range(0, 10_000, 10)]
print(f'best of 10 runs is the minimum cut {sum(c[0] == 4 for c in best_of_10)} times out of 1,000')
print(f'runs needed for 99% with only the guarantee: {math.ceil(math.log(100) / -math.log(1 - 2 / 56))}')
# minimum cut found in 3228 of 10,000 runs
# guaranteed at least 2 / (n (n - 1)) = 0.0357 per run
# best of 10 runs is the minimum cut 978 times out of 1,000
# runs needed for 99% with only the guarantee: 127

在示例上运行 10,000 次，最小割出现了 3,228 次，约占 32%，是保证值 3.6% 的九倍。保留 10 次运行中的最优结果，在 1,000 次试验中有 978 次找到了它。这个保证是最坏情况：如果只依赖它，在 8 个顶点上需要 127 次运行才能达到 99% 的置信度。Karger 的界还有一个惊人的推论。每个最小割被找到的概率至少为 2 / (n (n - 1))，而这些事件不可能同时发生，所以一个图最多有 n (n - 1) / 2 个最小割。一个有 n 个顶点的环恰好有这么多：删除它的任意两条边都是一个最小割。

David Karger 和 Clifford Stein 在 1996 年改进了这一方法：只收缩到中途，然后在两个副本上递归，从而以高概率在 O(n2 log3 n) 时间内找到最小割。Karger 后来又给出了一种运行时间与边数近乎线性的算法。

8. 选用哪种算法

实践中：对于两个给定顶点之间的割，运行一次最大流。对于无向图的全局最小割，Stoer-Wagner 是标准的确定性选择，也是 NetworkX 等库所实现的算法。当图很大、计算可以分散到多台机器上，或者你需要所有最小割而不只是一个时，就该使用 Karger 算法。

9. 有向图与点割

在有向图中，割 (S, V \ S) 只计算从 S 指向另一侧的弧；反向的弧对断开它没有帮助。Stoer-Wagner 和 Karger 算法依赖对称性，因此不适用。全局最小割仍然可以用最大流求出：从一个固定顶点到其他每个顶点，再反向各做一次；Jianxiu Hao 和 James Orlin 在 1994 年展示了如何在大约一次流计算的时间内完成这一工作。

有时问题在于删除哪些顶点而不是哪些边：即那些一旦故障就会使网络分裂的路由器。这样的最小集合给出点连通度，一个标准技巧可以把它归结为边割：把每个顶点拆成“入”和“出”两个副本，用一条容量为 1 的边连接。删除后会使图不连通的单个顶点称为割点，起同样作用的单条边称为桥。两者都可以不用流在线性时间内找到，正如关于连通分量、桥与割点的指南所解释的。

10. 最小割的应用

• 网络可靠性。通信网络或电力网络的全局最小割就是它的最薄弱之处：一旦故障就会使它分裂的最少链路或最小容量。最小 s-t 割是两个站点之间的瓶颈，就像示例中那样。
• 图像分割。把每个像素作为一个顶点，与它的相邻像素相连，相似像素之间的链路权重大，再添加一个代表“物体”的源点和一个代表“背景”的汇点。最小 s-t 割沿着切断最弱链路的边界把物体与背景分开。D. M. Greig、B. T. Porteous 和 A. H. Seheult 在 1989 年首次把最小割用于图像分析，用来复原有噪声的二值图像；Zhenyu Wu 和 Richard Leahy 在 1993 年把它们用于分割；而 Yuri Boykov 的交互式图割使这一方法成为计算机视觉中的标准工具。
• 聚类。最小割在相似度图最薄弱的地方把它分开。单独使用时，它往往会切下几个连接松散的点，这就是 Jianbo Shi 和 Jitendra Malik 引入归一化割的原因，它用割的权重除以每一侧的大小。
• 项目选择。选择那些能赚钱但需要昂贵前提条件的项目，是一个伪装起来的最小割问题：有利可图的项目挂在源点上，成本挂在汇点上，前提条件变成容量无限的弧。关于资本预算的指南就是用这种方法求解这样一个投资组合的。
• 体育赛事淘汰。在剩余比赛已知的情况下，一支球队能否仍然获得第一名，是一个最大流问题，而最小割可以证明答案是“否”，正如 Benjamin Schwartz 在 1966 年针对棒球所展示的那样。

相反的问题，即最大割，要求找出跨越边尽可能多的划分，它看起来相似，却是 NP 难的。最小化割之所以容易，是因为它与流对偶；最大化割则没有这样的结构。

11. 近期进展

最小割领域出现了算法研究中一些最引人注目的近期进展。2015 年，Ken-ichi Kawarabayashi 和 Mikkel Thorup 找到了一种针对简单无权图全局最小割的确定性算法，运行时间接近线性。2021 年，Jason Li 把确定性的几乎线性时间推广到了带权图。2022 年，Li Chen、Rasmus Kyng、Yang P. Liu、Richard Peng、Maximilian Probst Gutenberg 和 Sushant Sachdeva 证明，整数容量的最大流，以及随之而来的最小 s-t 割，可以在几乎线性的时间 m1 + o(1)内计算出来，这一成果获得了 FOCS 2022 最佳论文奖。这些算法尚未被实际软件采用，但它们从原理上回答了这些问题能被多快地求解。

12. 常见错误

13. 术语表

15. 参考文献

上文中的定理、算法和归属均来自以下文献，按时间顺序排列。

1. Menger, K. (1927). "Zur allgemeinen Kurventheorie." Fundamenta Mathematicae 10，96 至 115 页。
2. Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1)，150 至 168 页。
3. Harris, T. E. 和 Ross, F. S. (1955). Fundamentals of a Method for Evaluating Rail Net Capacities. 研究备忘录 RM-1573。圣莫尼卡：RAND Corporation。
4. Elias, P., Feinstein, A. 和 Shannon, C. E. (1956). "A Note on the Maximum Flow Through a Network." IRE Transactions on Information Theory 2(4)，117 至 119 页。
5. Ford, L. R. 和 Fulkerson, D. R. (1956). "Maximal Flow Through a Network." Canadian Journal of Mathematics 8，399 至 404 页。
6. Gomory, R. E. 和 Hu, T. C. (1961). "Multi-Terminal Network Flows." Journal of the Society for Industrial and Applied Mathematics 9(4)，551 至 570 页。
7. Schwartz, B. L. (1966). "Possible Winners in Partially Completed Tournaments." SIAM Review 8(3)，302 至 308 页。
8. Edmonds, J. 和 Karp, R. M. (1972). "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems." Journal of the ACM 19(2)，248 至 264 页。
9. Greig, D. M., Porteous, B. T. 和 Seheult, A. H. (1989). "Exact Maximum A Posteriori Estimation for Binary Images." Journal of the Royal Statistical Society, Series B 51(2)，271 至 279 页。
10. Nagamochi, H. 和 Ibaraki, T. (1992). "Computing Edge-Connectivity in Multigraphs and Capacitated Graphs." SIAM Journal on Discrete Mathematics 5(1)，54 至 66 页。
11. Karger, D. R. (1993). "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-cut Algorithm." 载于 Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms，21 至 30 页。
12. Wu, Z. 和 Leahy, R. (1993). "An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation." IEEE Transactions on Pattern Analysis and Machine Intelligence 15(11)，1101 至 1113 页。
13. Hao, J. 和 Orlin, J. B. (1994). "A Faster Algorithm for Finding the Minimum Cut in a Directed Graph." Journal of Algorithms 17(3)，424 至 446 页。
14. Karger, D. R. 和 Stein, C. (1996). "A New Approach to the Minimum Cut Problem." Journal of the ACM 43(4)，601 至 640 页。
15. Stoer, M. 和 Wagner, F. (1997). "A Simple Min-Cut Algorithm." Journal of the ACM 44(4)，585 至 591 页。
16. Karger, D. R. (2000). "Minimum Cuts in Near-Linear Time." Journal of the ACM 47(1)，46 至 76 页。
17. Shi, J. 和 Malik, J. (2000). "Normalized Cuts and Image Segmentation." IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8)，888 至 905 页。
18. Boykov, Y. 和 Jolly, M.-P. (2001). "Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images." 载于 Proceedings of the 8th IEEE International Conference on Computer Vision，105 至 112 页。
19. Schrijver, A. (2002). "On the History of the Transportation and Maximum Flow Problems." Mathematical Programming 91(3)，437 至 445 页。
20. Kawarabayashi, K. 和 Thorup, M. (2015). "Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time." 载于 Proceedings of the 47th ACM Symposium on Theory of Computing，665 至 674 页。
21. Li, J. (2021). "Deterministic Mincut in Almost-Linear Time." 载于 Proceedings of the 53rd ACM Symposium on Theory of Computing，384 至 395 页。
22. Chen, L., Kyng, R., Liu, Y. P., Peng, R., Probst Gutenberg, M. 和 Sachdeva, S. (2022). "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time." 载于 Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science，612 至 623 页。