无向图最小割问题取得新突破，谷歌研究获SODA 2024最佳论文奖

王林

发布时间：2024-04-17 21:58:01

826人浏览过

来源于机器之心

转载

谷歌博客放出新研究，求解无向图的最小割问题。

1996 年，美国计算机科学家 David R Karger 连同其他研究者在论文《 A new approach to the minimum cut problem》中提出了一个令人惊讶的随机算法 Karger 算法，其在理论计算机科学中非常重要，尤其适用于大规模图的近似最小割问题。

Karger 算法可以在时间为 O (m log^3n) 的图中找到一个最小割点，他们将这个时间称之为近线性时间，意思是线性乘以一个多对数因子。

在谷歌刚刚更新的一篇博客中，他们介绍了之前发布的一篇论文《 Deterministic Near-Linear Time Minimum Cut in Weighted Graphs 》，研究获得了 ACM-SIAM SODA24 最佳论文奖。文章详细阐述了一个几乎是线性时间内（而不是近线性时间）运行的新算法，这个算法是确定性的，能够可靠地找到正确的最小割，改进了之前可能无法保证结果正确或只适用于简单图的算法。可以说这是自 Karger 著名的随机化算法以来的重大发现。

论文地址：https://arxiv.org/pdf/2401.05627.pdf
论文标题：Deterministic Near-Linear Time Minimum Cut in Weighted Graphs

注：最小割问题（通常称为最小割）是关于图连通性的基本结构问题，它一般关注的是断开网络最简单的方法是什么？在图论中，去掉其中所有边能使一张网络流图不再连通（即分成两个子图）的边集称为图的割，一张图上最小的割称为最小割。

^{一张图及其两个割：红色点线标出了一个包含三条边的割，绿色划线则表示了这张图的一个最小割（包含两条边）。}

方法介绍

关于最小割问题，Karger 在 1996 年开创性的给出了一个近乎线性的时间随机算法，该算法能够以较高的概率找到最小割，并且该工作还给出了一个关键见解，即存在一个更小的图，它在很大程度上保留了所有割的大小。

这个发现是很有用的，因为可以使用较小的图作为输入来运行较慢的算法，并且较慢的运行时间（就较小的图的大小而言）仍然可以与原始（较大）图的大小接近线性。

事实上，关于最小割问题的许多结构发现都是沿着这个方向进行的。

谷歌是这样做的，从具有 n 个节点的图 G 开始，然后依据论文《 Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs 》（作者为 Benzur、Karger）提出的割保留稀疏化方法，证明了可以构造一个边数更少的稀疏加权图 G'，且在这个图上，几乎所有割的大小与原图 G 中相应割的大小大致相同。

这个概念可以通过以下例子来说明：原始图由两个通过单一边连接的完全图组成，而稀疏化后的图边数更少，但边的权重更大，同时所有割的大小大致得以保留。

☞☞☞AI 智能聊天, 问答助手, AI 智能搜索, 免费无限量使用 DeepSeek R1 模型☜☜☜

无向图最小割问题取得新突破，谷歌研究获soda 2024最佳论文奖

为了构建这种较稀疏的图，Benzur 和 Karger 采用了独立采样边的方法。在这种方法中，图 G 中的每条边都有一定概率被包含在图 G' 中，并且其在 G' 中的权重会根据采样概率的倒数进行放大（例如，如果一条原权重为 1 的边以 10% 的概率被包含，则其权重调整为 10）。结果表明，这种非常简单（几乎是线性时间）的方法具有很高的成功概率，可以构建出保持割的图稀疏化。

然而，Karger 算法是一种蒙特卡洛算法，即输出可能小概率不正确，并且除了与实际已知的最小割进行比较之外，没有已知的方法可以判断输出是否正确。

因此，研究人员一直在努力探索解决近线性时间确定性算法开放问题的方法。由于 cut-preserving 图稀疏化的构造是 Karger 算法中唯一随机的组成部分，因此一种方法是在近线性时间内找到稀疏化的确定性构造（也称为去随机化）。

2015 年，Kawarabayashi 和 Thorup 实现了一个重要的里程碑 —— 找到针对简单图（即每对节点之间至多有一条边且所有边权重等于 1 的图）的确定性近线性时间算法。

该研究得出一个关键思路，即最小割和另一个重要的图结构（称为「low-conductance cut」）之间存在一些联系。这种联系对于后来在一般边权重图上去随机化 Karger 算法至关重要，并帮助谷歌得出了新算法。

最小割和 low-conductance cut 的对齐

图割 S 的 conductance 定义为 S 的 cut 大小与 S 的 volume 之比（假设 S 是切口的较小体积侧且非空），其中 S 的 volume 是 S 中节点的度数。

low-conductance 的 cut S 直观地捕获了网络中的瓶颈，因为只有少量边（相对于其 volume）将 S 连接到图的其余部分。图的 conductance 被定义为图中任何 cut 的最小 conductance，并且大 conductance 的图（也称为扩展图）被认为是良好连接的，因为内部没有瓶颈。

^{红色虚线表示 cut 大小为 2，较小的一侧（底部）volume 为 24，因此其 conductance 为 1/12，这也是图的 conductance。}

Kawayabarashi 和 Thorup 观察到，在最小节点度数较大的简单图中，任何非平凡（即两侧至少有两个节点）最小割都必须具有 low conductance。根据这一观察，如果可以将图划分为连接良好的簇（cluster），则划分必须与每个非平凡最小割一致，因为每个簇必须完全位于每个 cut 的一侧。然后，将每个簇收缩为一个节点，并处理较小的图，其中原始图的所有非平凡最小割都完好无损。

然而，对于加权图，上述观察不再成立，并且简单图情况中使用的相同划分可能与非平凡最小割不完全一致。

如下图所示，Jason Li 2021 年观察到，这种划分仍然与非平凡最小割大致一致。特别地，对于非平凡最小割 S，存在与 S 相差不大的 cut S'，使得 S' 与簇一致。Jason Li 进一步观察到，可以利用划分的这种特性来有效地去随机化 cut-preserving 图稀疏化的构造。

无向图最小割问题取得新突破，谷歌研究获SODA 2024最佳论文奖

歌者PPT

歌者PPT，AI 写 PPT 永久免费

下载

谷歌设计的新算法旨在构建一种划分，来制定最小割的用例。与 Jason Li 在之前的工作中使用的更通用的现成方法相比，谷歌的这项研究更加精确、更加快捷。新研究在保证精度的同时在运行时间上也进行了优化，最终实现了针对最小割问题的近线性时间确定性算法。

^{参考链接：https://research.google/blog/solving-the-minimum-cut-problem-for-undirected-graphs/}

Gemini 3.1 Pro— 谷歌推出的最新AI模型，主打复杂推理

Gemini 3 Deep Think— 谷歌推出的专用推理模型

PaperBanana— 北大联合谷歌推出的AI学术插图自动生成框架

RynnBrain— 阿里达摩院开源的具身智能大脑基础模型

免费AI翻译哪家强？DeepSeek/豆包/谷歌翻译横向对比

谷歌浏览器

谷歌浏览器Google Chrome是一款可让您更快速、轻松且安全地使用网络的浏览器。Google Chrome的设计超级简洁，使用起来得心应手。这里提供了谷歌浏览器纯净安装包，有需要的小伙伴快来保存下载体验吧！

下载

相关专题

li是什么元素

li是HTML标记语言中的一个元素，用于创建列表。li代表列表项，它是ul或ol的子元素，li标签的作用是定义列表中的每个项目。本专题为大家li元素相关的各种文章、以及下载和课程。

436

2023.08.03

页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章，大家可以免费体验。

499

2023.08.14

http与https有哪些区别

http与https的区别：1、协议安全性；2、连接方式；3、证书管理；4、连接状态；5、端口号；6、资源消耗；7、兼容性。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

2915

2024.08.16

TypeScript类型系统进阶与大型前端项目实践

本专题围绕 TypeScript 在大型前端项目中的应用展开，深入讲解类型系统设计与工程化开发方法。内容包括泛型与高级类型、类型推断机制、声明文件编写、模块化结构设计以及代码规范管理。通过真实项目案例分析，帮助开发者构建类型安全、结构清晰、易维护的前端工程体系，提高团队协作效率与代码质量。

2026.03.13

Python异步编程与Asyncio高并发应用实践

本专题围绕 Python 异步编程模型展开，深入讲解 Asyncio 框架的核心原理与应用实践。内容包括事件循环机制、协程任务调度、异步 IO 处理以及并发任务管理策略。通过构建高并发网络请求与异步数据处理案例，帮助开发者掌握 Python 在高并发场景中的高效开发方法，并提升系统资源利用率与整体运行性能。

2026.03.12

C# ASP.NET Core微服务架构与API网关实践

本专题围绕 C# 在现代后端架构中的微服务实践展开，系统讲解基于 ASP.NET Core 构建可扩展服务体系的核心方法。内容涵盖服务拆分策略、RESTful API 设计、服务间通信、API 网关统一入口管理以及服务治理机制。通过真实项目案例，帮助开发者掌握构建高可用微服务系统的关键技术，提高系统的可扩展性与维护效率。

174

2026.03.11

Go高并发任务调度与Goroutine池化实践

本专题围绕 Go 语言在高并发任务处理场景中的实践展开，系统讲解 Goroutine 调度模型、Channel 通信机制以及并发控制策略。内容包括任务队列设计、Goroutine 池化管理、资源限制控制以及并发任务的性能优化方法。通过实际案例演示，帮助开发者构建稳定高效的 Go 并发任务处理系统，提高系统在高负载环境下的处理能力与稳定性。

2026.03.10

Kotlin Android模块化架构与组件化开发实践

本专题围绕 Kotlin 在 Android 应用开发中的架构实践展开，重点讲解模块化设计与组件化开发的实现思路。内容包括项目模块拆分策略、公共组件封装、依赖管理优化、路由通信机制以及大型项目的工程化管理方法。通过真实项目案例分析，帮助开发者构建结构清晰、易扩展且维护成本低的 Android 应用架构体系，提升团队协作效率与项目迭代速度。

2026.03.09

JavaScript浏览器渲染机制与前端性能优化实践

本专题围绕 JavaScript 在浏览器中的执行与渲染机制展开，系统讲解 DOM 构建、CSSOM 解析、重排与重绘原理，以及关键渲染路径优化方法。内容涵盖事件循环机制、异步任务调度、资源加载优化、代码拆分与懒加载等性能优化策略。通过真实前端项目案例，帮助开发者理解浏览器底层工作原理，并掌握提升网页加载速度与交互体验的实用技巧。

102

2026.03.06

热门下载

网站特效

网站源码

网站素材

前端模板