迄今最快的图着色方式

研究者设计出了一种方案，能以近乎最快的速度对图的边着色。

Steve Nadis 著

左   芬    译

【译注：原文2025年5月12日刊载于QuantaMagazine，链接见文末。】

这儿有一个骇人的任务：你被任命负责纽约附近纽瓦克机场的航班交通控制。你需要确保每架飞机能在跑道和登机口之间滑行，而不撞到任何其它飞机。

让我们借用强大的数学来处理你的问题。首先，为你的机场构建一个巨大的示意地图。对于每条跑道、滑行道以及登机口，画一个点。接着，对于每架飞机，画一条线连接这些点：如果飞机得从4L跑道沿K滑行道至C80登机口，就画一条线连接跑道4L，滑行道K以及登机口C80。

接着是最重要的环节：避免冲突。你会注意到每个物理地点都有大量飞机进出其中——有大量线连往你的地图的每个点，而研究者把这个就叫做图。为了确保没有两架飞机同一时刻在同一地点，你可以对你的线着色，并要求连到同一个点的任两条线颜色均不相同。这些颜色代表着时刻，通过要求汇聚到一个点的所有颜色均不相同，你就避免了两架飞机在同一时刻处在同一个位置。

现在你需要做的就剩下填充这些颜色了。对于一座机场而言，你可能手算就可以做到，哪怕对于纽瓦克这样的大型机场。不过研究者通常分析具有数十亿甚至更多连线的图。因此他们会开发算法来对这些图指派颜色。

然而，这些算法是缓慢的，并且已经“原地踏步了40年了”，加拿大滑铁卢大学计算机科学家Sepehr Assadi称。

对于某些图，Sepehr Assadi给出了比之前最快的算法还要快得多的着色方法。

然而，2024年，在相距数天时间内，两个不同的研究小组就都想出了比旧标准显著更快的新算法。如今，在6月即将举行的2025年度计算理论年会上将提交的一篇论文走得更远。它描述了一个近乎最优的算法——差不多近其可能地快了。惊人的是，这一新算法完全不依赖于你的图中的点的数目，而只依赖于边数。所以你的机场有多大已经无关紧要了，只有飞机经过路线的数目才要紧。

这篇新论文“几乎彻底解决了这一问题，”加州大学洛杉矶分校数学家Anton Bernshteyn说道，“几乎没人会在几年前预料到这样一个里程碑式的进展。”

活在边上

1964年，一位名叫Vadim Vizing的数学家证明了一个惊人结果：无论你的图多大，很容易弄清需要多少种颜色才能给它着色。只需要找出连到单个点（或者叫顶点）的线的最大数目，再加1就行。

不过，如何去着好这些颜色事实上又是另一个难题了。Vizing想出了他自己的着色算法，但它很慢。他开始审视还差一条边就完全着好色的图，分析给最后一条边着色需要的时间。给那条边着色意味着可能改变与它相邻的边的颜色，进一步又会改变跟它们相邻的边的颜色，并且沿着这一路线持续下去。Vizing算出了给单条边着色会需要——至多——正比于总顶点数目，他记作n，的时间量。如果总共有m条边，Vizing的算法对于着色整个图给出的时间正比于m与n的乘积。

这一结果维持了20年，直到1980年代的工作才将边着色时间降下来。新的结果正比于m与n的平方根的乘积。但这些改进背后的技术并没有带来更多的进展。其他研究者也没能进一步改进它们，于是发展停滞了。

Martín Costa参与的团队多次降低了图着色算法的时间。

接下来，2024年五月，Assadi在科学预印本网站arxiv.org提交了一篇文章，展示如何将图着色的时间降到n²的水平——这一因子仅仅依赖于顶点的数目。对于某些图来说，顶点数目会远小于边的数目，因此这是一个巨大的改进。

就在差不多同一时间，跟Assadi不相关的另一个团队公布了他们自己的结果，将边着色时间降到了m乘以n的立方根的水平。他们的做法是找到着色单条边的一种稍快方法。在一篇后续文章中，该团队做了进一步的改善，得到正比于m与n的四次方根的乘积的总运行时间。

在夏天期间，该团队开始与Assadi以及一个新的成员，西北大学的Sohei Behnezhad，合作。不过他们不再为逐步的改进而努力，转而寻求一种更基本的收益。“一旦我们找到一种方法超出了那个【旧结果】，”Assadi说道，“我们认为前方就不存在任何根本性的障碍了。”

新形成的团队决定瞄准终极目标：理论上的最短时间。你遍历整个图，仅仅看看它长什么样子——去看看这条边是红色，下条边是蓝色，等等——的最短时间就是m，边的数目。而你对边着色不可能比阅读边更快，这一“线性时间”m也就是可以达到的最短着色时间。

不过要达到这一速度，他们无法依赖在之前这些文章中用到的同种战术了。“我们清楚我们至今为止引入的技术只对某种改进有用，但没有哪种真正强大到将算法降到近线性时间，”身为沃里克大学博士生，同时也是包括去年进展在内的数篇边着色文章共同作者的Martín Costa说道。只要他们还对实现那一目标抱有任何希望，Costa补充道，“我们就确实需要采取一种截然不同的方法。”

填涂底色

团队意识到，从2024年这些文章一直回溯到Vizing本人为止，所有这些策略都受限于同一个瓶颈。回顾一下，Vizing假定最坏情形方案——给图中剩下的最后一条边着色，接着不得不改变所有其它与其相邻的边的颜色。“之前的工作都聚焦于争取更快地着色最后一条边，”Assadi说道，“于是我们转而使用了另一种方法。”他们不再试图更快地着色一条边，而是想弄清如何快速地在几乎同一时间为多条边着色。

Soheil Behnezhad与Costa, Assadi及其他人一道设计出了一种尽可能快为图着色的算法。

为此，团队从一个不太可能的场景——房子翻新——中借用了一个概念。如果你打算重刷你的墙，你会先涂上一层底漆让它们回到中性色调。同样，研究者们尝试“底色化”图——把它变成一种新的状态，从而易于着色。他们使用随机化技术来实现这一点，本质上也就是依靠大量抛硬币的结果来着色几乎整个图，只战略性地留下某些边空白着。在底色化后，这些遗留的区域可以简单地且近乎同时地着好色。团队的快速新算法可以“接近线性地”——在m乘以m的对数这个水平上——给图着色。

“这是个突破——一个惊人的结果，”普林斯顿大学计算机科学家，同时也是Turing奖得主的Robert Tarjan说道。团队的底色化图的策略称得上是开创性的。“这一新想法有点颠覆一切。”Tarjan称。

海法市以色列理工学院的计算机科学家David Wajc觉得这一结果很“鼓舞人心”——是自1960年代以来的巅峰。

寻求完美

尽管理论家们已经在庆祝了，这一结果是否会产出任何实际生活中的加速仍不明朗。虽然理论家们普遍不关心常数因子，“在实用中，它们是有干系的，”Behnezhad提醒道。他们获得的运行时间正比于，或者等价地，是一个常数乘以。“在这个算法里，那个常数似乎很小，”他说，“这暗示该算法可能实用。”

与此同时，团队开始考虑如何将他们的结果进一步推进。研究者们想要知道，是否不依赖任何随机性也能得到近线性时间。“这个在理论上是有意义的，并且能知道你的算法总是会刚好以这个时间运行，没有任何可能性会变慢，总是更好的。”Costa说道。

此外，团队想要知道是否能从他们的运行时间里把额外的对数因子移除掉，从而让结果不再是近线性，而是精确线性。“这正是我们拥有的和我们的最佳期望之间的差异，”Assadi说道，“但只有极少的图论问题我们能真正移除掉那个因子。”

在Tarjan看来，消除随机性和对数因子当然是有趣的，“但这些都是巨大的挑战，”他说，“我觉得在可见的未来目前这一结果都将维持下去。”

原文链接：

https://www.quantamagazine.org/the-fastest-way-yet-to-color-graphs-20250512/