目前最快的 Graphs 着色方法
The Fastest Way Yet to Color Graphs
作者： Steve Nadis 发布日期： 2025年5月12日
研究人员设计了一种为 graph 的边着色的方案，其速度几乎达到了理论上的最快速度。
引言
By Steve Nadis 特约撰稿人
发布日期： 2025年5月12日
下面是一个令人紧张的场景：你负责纽约附近纽瓦克机场的空中交通管制。你需要确保每架飞机都可以在跑道和停机坪之间滑行，而不会撞到其他飞机。
让我们运用数学的力量来解决您的问题。首先，创建机场的大型抽象地图。对于每条跑道、滑行道和停机坪，都标记一个点。然后，对于每架飞机，绘制一条连接这些点的线：如果一架飞机必须从 4L 跑道沿 K 滑行道到 C80 停机坪，则绘制一条连接 4L 跑道、K 滑行道和 C80 停机坪的点的线。
现在是最重要的部分：避免碰撞。您会注意到，每个物理位置都有大量飞机进出——很多线连接到地图上的每个点，研究人员称之为 graph。为了确保没有两架飞机在同一时间位于同一地点，您可以为每条线着色，并要求对于每个点，连接到它的任意两条线不能具有相同的颜色。这些颜色代表时间；通过要求汇聚于单个点的所有颜色都不同，可以防止飞机同时位于同一地点。
现在您需要做的就是填充颜色。对于机场而言，即使是纽瓦克这样的大型机场，也可能手动完成。但研究人员通常分析具有数十亿甚至更多连接的 graph。因此，他们开发了为 graph 分配颜色的 algorithms。
然而，这些 algorithms 速度很慢，并且“在过去 40 年里或多或少地停滞不前”，加拿大滑铁卢大学的计算机科学家 Sepehr Assadi (opens a new tab)说。
Sepehr Assadi 展示了如何比以前最快的 algorithm 更快地为某些 graph 着色。
Joe Petrik
然后在 2024 年，短短几天内，两个不同的研究小组提出了新的 algorithms，这些 algorithms 比旧的标准算法快得多。现在，一篇将在 2025 年计算机理论研讨会上发表的论文更进一步。它描述了一个几乎最优的 algorithm (opens a new tab)——一个实际上尽可能快的 algorithm。令人惊讶的是，这种新的 algorithm 根本不依赖于 graph 中的点数，而只依赖于线数。机场有多大已经不再重要，重要的是飞机采取的路径数量。
加州大学洛杉矶分校的数学家 Anton Bernshteyn (opens a new tab)说，这篇新论文“几乎完全解决了这个问题”。这是“即使在几年前也很少有人预测到的一个里程碑”。
在线上生活
1964 年，一位名叫 Vadim Vizing 的数学家证明了一个令人震惊的结果：无论 graph 有多大，都很容易计算出需要多少颜色来为其着色。只需查找连接到单个点（或顶点）的最大线（或边）数，然后加 1 即可。
然而，如何填充这些颜色的问题，却被证明是另一回事。Vizing 提出了他自己的着色 algorithm，但它很慢。他首先考虑为已完全着色的 graph 中仅剩余的一条边着色所需的时间。为该边着色可能意味着更改与其相邻边的颜色，并更改与其相邻的边的颜色，依此类推。Vizing 计算出，为单个边着色最多可能需要与顶点总数成正比的时间，他将其标记为 n。如果总共有 m 条边，则 Vizing 的 algorithm 得出的为整个 graph 着色的时间与 m 乘以 n 的乘积成正比。
这个值保持了大约 20 年，直到 20 世纪 80 年代的工作降低了 (opens a new tab)边着色时间 (opens a new tab)。新值与 m 乘以 n 的平方根成正比。但是，这些改进背后的技术并没有带来其他进展。其他研究人员无法进一步改进它们，进展停滞不前。
Martín Costa 是一个降低 graph 着色 algorithm 运行时的团队的成员。
Facundo Costa
然后，在 2024 年 5 月，Assadi 在科学预印本网站 arxiv.org 上发表了一篇论文，展示了如何为 graph 着色 (opens a new tab)，其数量级为 n 2 时间——一个仅取决于顶点数量的因子。对于某些顶点数量远小于边数的 graph 来说，这是一个巨大的改进。
大约在同一时间，一个与 Assadi 无关的团队发布了自己的结果，将边着色时间缩短到 m 乘以 n 的立方根的数量级 (opens a new tab)。他们通过找到一种稍微快一点的为单个边着色的方法来实现的。在一篇后续论文中，该团队进行了进一步的改进 (opens a new tab)，从而导致总运行时间与 m 乘以 n 的四次方根成正比。
在夏天，该团队开始与 Assadi 和东北大学的一位新团队成员 Soheil Behnezhad (opens a new tab)合作。但是，他们并没有努力进行增量改进，而是寻求更根本的收益。“一旦我们找到了一种方法来克服那个 [旧结果]，”Assadi 说，“我们就没有看到任何根本性的障碍。”
这个新成立的团队决定瞄准最终目标：理论上的最短时间。您可以浏览整个 graph 并查看其外观（以注意这条边是红色，下一条边是蓝色等等）的最快速度仅仅是 m，即边数。由于您为边着色的速度不能快于读取它们的速度，因此该“线性时间”m 也是最快的着色时间。
但是要达到这个速度，他们不能依赖于他们在以前的论文中使用的相同策略。“我们意识到，我们迄今为止引入的技术对于获得某种改进是有用的，但它们实际上都没有足够的能力将 algorithm 降低到接近线性的时间，”华威大学的博士生 Martín Costa (opens a new tab)说，他是几篇关于边着色的论文的合著者，包括去年的进展。Costa 补充说，如果他们希望实现该目标，“我们实际上必须采取完全不同的方法。”
绘画入门
该团队意识到，从 2024 年的论文到 Vizing 本人，所有策略都受到了相同的瓶颈的困扰。回想一下，Vizing 假设了最坏的情况——为 graph 中最后一条可能的边着色，然后不得不更改与之相连的每条其他边的颜色。“以前的工作重点是尝试更快地为最后一条边着色，”Assadi 说。“因此，我们使用了另一种方法。”他们不想尝试更快地为一条边着色，而是想看看如何几乎同时为多条边着色。
Soheil Behnezhad 与 Costa、Assadi 等人一起设计了一种以几乎最快的速度为 graph 着色的 algorithm。
Zlata Rezanova
为此，该团队从一个不太可能的来源借用了一个概念：家居装修。如果您要重新粉刷墙壁，您首先要涂上一层底漆，使其恢复中性。以同样的方式，研究人员试图“启动” graph——使其进入一种更易于着色的新状态。他们使用 随机化技术 来做到这一点，基本上依靠无数次抛硬币的结果来为 graph 的大部分着色，同时有策略地留下某些未着色的边。在启动之后，这些最后区域可以简单且几乎同时地进行绘制。该团队快速的新 algorithm 可以“接近线性地”为 graph 着色——数量级为 m 乘以 m 的对数。
普林斯顿大学的计算机科学家 Robert Tarjan (opens a new tab)说：“这是一项突破——一个了不起的成果。”他是 图灵奖 (opens a new tab)的获得者，该奖项被认为是该领域的最高荣誉。该团队的启动 graph 的策略已被证明具有突破性。“这个新想法改变了一切，”Tarjan 说。
以色列海法理工学院的计算机科学家 David Wajc (opens a new tab)认为该结果“鼓舞人心”——是追溯到 20 世纪 60 年代的数十年研究的结晶。
超越近乎完美
尽管理论家们可能正在庆祝，但目前尚不清楚该结果是否会转化为任何现实生活中的加速。虽然理论家通常不在乎常数因子，但 Behnezhad 指出，“在实践中，它们确实很重要”。他们实现的运行时间与 m log m 成正比，或者等效地，与常数乘以 m log m 成正比。“在该 algorithm 中，该常数似乎非常小，”他说。“这是一个表明该 algorithm 可能具有实用性的迹象。”
相关文章:
与此同时，该小组正在考虑如何进一步推进其结果。研究人员希望看看他们是否可以在不依赖任何随机性的情况下实现接近线性的时间。“这在理论上很有趣，而且很高兴知道您的 algorithm 将始终以完全相同的时间运行，并且没有可能变慢的机会，”Costa 说。
此外，该团队希望看看是否有可能从他们的运行时间中删除额外的对数项，从而使结果不仅接近线性，而且完全线性。“这就是我们得到的与人们可以期望的最佳结果之间的区别，”Assadi 说，“但是我们实际上可以删除该项的 graph 问题很少。”
对于 Tarjan 来说，消除随机性和对数项肯定会很有趣，“但这些都是巨大的挑战，”他说。“我认为该结果将在可预见的未来成为最先进的技术。”