[BUG] HLPP 算法可能有误

[hly1204]

• 我正在着手修复这个问题

我正在访问这个页面（最好带链接）

https://oi-wiki.org/graph/flow/max-flow/

我发现页面有这样的问题

其中提到使用优先队列，但是优先队列的删除操作好像没办法做到常数时间（如果是斐波那契堆的话，插入可以做到常数时间）。

论文 http://www.cs.cornell.edu/~eva/Network.Flow.Algorithms.pdf page 121 （右上角是页数编号）提到

Any representation of the set of active vertices that allows insertion, deletion,
and access to some active vertex in 0(1) time results in an O(n^2m) running time
for the discharge-based algorithm, by Lemmas 2.2.6 and 2.3.2. (Pushes can be
implemented in O(1) time per push.)

这是对于通用的预留推进算法的复杂度，阅读前文引理 2.2.6 会发现其瓶颈在于所谓的不饱和推送的次数，不饱和推送就是推出去这条边没办法把剩余容量填满，意味着其溢出函数小于这条边的剩余容量了，那么此时对于一个优先队列必然需要删除这个节点，而删除操作没办法做到常数。后文提到 HLPP 与 FIFO 的瓶颈也都在于这个不饱和推送的次数，我以前提过这个问题但我没读太多这篇文章，现在前半部分读下来基本可以确定确实是这个意思，审核的您也可以下论文看一下，我说的应该不是乱说。。所以要不然先把那个代码删了，然后使用优先队列这几句话也去掉吗。。我也没有找到什么代码可以替换所以就不 pull 了。

[black-desk]

我对最大流这一块不太熟悉, 这里大概记录一下我这两天简单查了一下以后知道的信息, 希望能帮助各位大佬理清一下情况. 英语不太好, 我会尽量注明出处, 要是有错请各位见谅.

算法名称

首先说一下, OI-wiki 里写的 "High Level Preflow Push" 这个说法很可能并不正确, 目前对于这种算法似乎没有特别一致的名称, 而 OI-wiki 中的名称的最初来源很可能是 这篇博客, 它发布于 2017-03-08 21:27:26, 我目前没有看到更早的.

而实际上, 谷歌学术 搜不到这个 "High Level Preflow Push"; wikipedia 则将这个算法称作 "Push–relabel algorithm with maximum distance vertex selection rule", 最接近的描述是 MIT 的一份 15-082j 的课件 中提到的 "highest level pushing algorithm", 另外在 An Analysis of the Highest-Level Selection Rule in thePreflow-Push Max-Flow Algorithm 中这个算法被称为 "Highest-Level Selection Rule in the Preflow-Push Max-Flow Algorithm"

算法导论 (第 26 章的本章注记中) 和 wikipedia 都指出提出该算法的论文为 Analysis of preflow push algorithms for maximum network flow. 我简单浏览该论文以后, 觉得这篇论文本身认为这种算法是在 A New Approach to the Maximum-Flow Problem 中提出的, 而他们的工作是给出了一个更紧的复杂度上界.

有趣的是: A New Approach to the Maximum-Flow Problem 将该算法称为 "maximum-distance method"; Analysis of preflow push algorithms for maximum network flow 中则主要将该算法称为 "the highest distance preflow push algorithm".

也许是由于 A New Approach to the Maximum-Flow Problem 中有将算法中用到的 distance 称作 label, 所以也有看到 highest label preflow push 的说法在 wikipedia 中 出现

中文互联网上, 搜索 "HLPP" 能够找到的最早文章是 这篇. 其中, 该算法也被称为 "Highest Label Preflow Push"

总结一下: 这个算法本身没有一个准确一致的名字, 本身叫法就很混乱, 但是目前 OI-wiki 中的 "High Level Preflow Push" 这个说法在英语世界似乎没有人在使用, 而且就语义来看, 至少也应该是 "Highest". "High Level Preflow Push" 大概率是 "Highest Label Preflow Push" 的误传.

实现

接下来是关于该算法是不是使用优先队列实现的问题.

目前我认为, 这个算法在 A New Approach to the Maximum-Flow Problem 中被提出, 最早在 Analysis of preflow push algorithms for maximum network flow 被证明其时间复杂度为 $O(n^2\sqrt{m})$, 而 An Analysis of the Highest-Level Selection Rule in thePreflow-Push Max-Flow Algorithm 中给出了另一种证明方式.

A New Approach to the Maximum-Flow Problem 中没有提到具体使用什么数据结构来实现这一选择节点的策略. 而 Analysis of preflow push algorithms for maximum network flow 中称:

The algorithm maintains all vertices having flow excess in a data structure so that it can easily select the highest distance vertex. This can be done at a cost of $O(1)$ per selected vertex by using a list based buckets data structure.

这段话出现在论文第 7 页, 是第三章结尾的最后一段. An Analysis of the Highest-Level Selection Rule in thePreflow-Push Max-Flow Algorithm 中则在文章的结尾处写到:

The bound on the running time follows easily from the previous theorem. Note that each push operation and each relabel operation can be implemented in $O(1)$ time. The highest-level selectionrule can be implemented by a "buckets data structure" with each bucket $i$ containing all nodes $w$ with $d(w) =i$. The total running time overhead for this is $O(nm)$

从这两段话基本可以确定这两篇证明复杂度的文章都认为需要使用 "buckets". 每次 push 和 relabel 都得是 $O(1)$ 的. 但是 OI-wiki 中目前有的那份模板里的 push 和 relabel 两个函数看起来不像是 $O(1)$ 的, 而且优先队列的 pop 操作的复杂度是 $O(log\ n)$ 的.

原作者 @sshwy 最好出来解释一下是怎么个情况 :)

[hly1204]

我对最大流这一块不太熟悉, 这里大概记录一下我这两天简单查了一下以后知道的信息, 希望能帮助各位大佬理清一下情况. 英语不太好, 我会尽量注明出处, 要是有错请各位见谅.

算法名称

首先说一下, OI-wiki 里写的 "High Level Preflow Push" 这个说法很可能并不正确, 目前对于这种算法似乎没有特别一致的名称, 而 OI-wiki 中的名称的最初来源很可能是 这篇博客, 它发布于 2017-03-08 21:27:26, 我目前没有看到更早的.

而实际上, 谷歌学术 搜不到这个 "High Level Preflow Push"; wikipedia 则将这个算法称作 "Push–relabel algorithm with maximum distance vertex selection rule", 最接近的描述是 MIT 的一份 15-082j 的课件 中提到的 "highest level pushing algorithm", 另外在 An Analysis of the Highest-Level Selection Rule in thePreflow-Push Max-Flow Algorithm 中这个算法被称为 "Highest-Level Selection Rule in the Preflow-Push Max-Flow Algorithm"

算法导论 (第 26 章的本章注记中) 和 wikipedia 都指出提出该算法的论文为 Analysis of preflow push algorithms for maximum network flow. 我简单浏览该论文以后, 觉得这篇论文本身认为这种算法是在 A New Approach to the Maximum-Flow Problem 中提出的, 而他们的工作是给出了一个更紧的复杂度上界.

有趣的是: A New Approach to the Maximum-Flow Problem 将该算法称为 "maximum-distance method"; Analysis of preflow push algorithms for maximum network flow 中则主要将该算法称为 "the highest distance preflow push algorithm".

也许是由于 A New Approach to the Maximum-Flow Problem 中有将算法中用到的 distance 称作 label, 所以也有看到 highest label preflow push 的说法在 wikipedia 中 出现

中文互联网上, 搜索 "HLPP" 能够找到的最早文章是 这篇. 其中, 该算法也被称为 "Highest Label Preflow Push"

总结一下: 这个算法本身没有一个准确一致的名字, 本身叫法就很混乱, 但是目前 OI-wiki 中的 "High Level Preflow Push" 这个说法在英语世界似乎没有人在使用, 而且就语义来看, 至少也应该是 "Highest". "High Level Preflow Push" 大概率是 "Highest Label Preflow Push" 的误传.

实现

接下来是关于该算法是不是使用优先队列实现的问题.

目前我认为, 这个算法在 A New Approach to the Maximum-Flow Problem 中被提出, 最早在 Analysis of preflow push algorithms for maximum network flow 被证明其时间复杂度为 $O(n^2\sqrt{m})$, 而 An Analysis of the Highest-Level Selection Rule in thePreflow-Push Max-Flow Algorithm 中给出了另一种证明方式.

A New Approach to the Maximum-Flow Problem 中没有提到具体使用什么数据结构来实现这一选择节点的策略. 而 Analysis of preflow push algorithms for maximum network flow 中称:

The algorithm maintains all vertices having flow excess in a data structure so that it can easily select the highest distance vertex. This can be done at a cost of $O(1)$ per selected vertex by using a list based buckets data structure.

这段话出现在论文第 7 页, 是第三章结尾的最后一段. An Analysis of the Highest-Level Selection Rule in thePreflow-Push Max-Flow Algorithm 中则在文章的结尾处写到:

The bound on the running time follows easily from the previous theorem. Note that each push operation and each relabel operation can be implemented in $O(1)$ time. The highest-level selectionrule can be implemented by a "buckets data structure" with each bucket $i$ containing all nodes $w$ with $d(w) =i$. The total running time overhead for this is $O(nm)$

从这两段话基本可以确定这两篇证明复杂度的文章都认为需要使用 "buckets". 每次 push 和 relabel 都得是 $O(1)$ 的. 但是 OI-wiki 中目前有的那份模板里的 push 和 relabel 两个函数看起来不像是 $O(1)$ 的, 而且优先队列的 pop 操作的复杂度是 $O(log\ n)$ 的.

原作者 @sshwy 最好出来解释一下是怎么个情况 :)

relabel 怎么实现到 O(1) 啊。。

[black-desk]

我确实不太清楚论文中这个话的意思, 不知道他说的 "each" 指的具体是什么东西. 我最近抽空把相关的文献都完整看一遍吧