切割路径及其剩余结构及其应用

《ACM Transactions on Algorithms》：Cut Paths and Their Remainder Structure, with Applications

有向图中的割路径定义为包含在所有指定节点间路径中的子路径，其结构分析可提升安全路径与多安全路径的算法效率，应用于生物信息学中的基因组排序问题，并建立最优计算复杂度。

　　

摘要AI 摘要

摘要

摘要

割弧或强桥是有向图中最重要的可达性概念之一。具体来说，在一个强连通图中，（$|V|=n$），割弧是指这样一个弧：$e\in E$，存在$|E|=m$，使得所有从$u$到$v$的路径都包含$e$。在本文中，我们将这一概念推广到割路径，即存在$u$和$v$的路径，所有从$u$到$v$的路径都包含$W$作为子路径。我们首先证明了割路径的各种性质，并定义了它们的剩余结构，利用这一结构提出了一种简单的$O(\mathrm{m)}$时间验证算法。进一步证明，一个图最多包含$O($n条长度最多为$($n2)的最大割路径，并提出了一种$O($n2)的枚举算法来查找最大割路径。

我们将割路径及其剩余结构应用于生物信息学中的几个可达性问题。如果一个路径是强连通图中每个节点覆盖路径的子路径，则称该路径为安全的。多重安全的定义类似，只是考虑节点覆盖的封闭路径$O($< />)时间算法来验证路径是否安全或多重安全。此外，通过在线性时间内同时计算割路径所有子路径的剩余结构，我们可以在$O($< />)时间内识别出所有多重安全路径。这比现有的最佳算法（运行时间为$O($< />2n3log?n)时间）有所改进。

AI 摘要

AI 生成摘要（实验性）

此摘要是使用自动化工具生成的，并非由文章作者编写或审核。它旨在帮助发现、帮助读者评估相关性，并协助相关领域的读者理解这项工作。它旨在补充作者提供的摘要，后者仍是文章的主要总结。完整文章是权威版本。点击这里了解更多。

点击这里对摘要的准确性、清晰度和实用性进行评论。您的反馈将有助于改进和未来版本的生成。

AI 生成的摘要

版本创建于2026年1月23日。

本文介绍了有向图中割弧的泛化概念——割路径，并发展了它们的理论属性和应用。割路径是指在某些节点对之间的所有路径中都出现的子路径，扩展了割弧这一在图连通性中至关重要的基本概念。

作者定义了割路径的剩余结构，该结构由四个部分组成，根据路径的可达性属性对图节点进行划分。这种结构提供了一种简单的线性时间验证方法，通过验证两个条件来检查路径是否为割路径：内部路径组件是否与路径的内部节点完全匹配，以及是否存在非连续路径节点之间的捷径。剩余结构被证明是分析连通性属性的强大工具。

本文对割路径的属性建立了严格的界限。每条割路径的长度最多为n-1，因为它们是使用不同节点的开路径。最多存在O(n)条最大割路径，总长度被限制在O(n2)以内，这两个界限都通过示例构造得到了证明。一种最优算法使用以任意节点为根的入分支和出分支树，在O(n2)时间内计算出所有最大割路径，利用了所有割路径必须位于这些树上并且只能通过根节点进行转换的观察结果。

本文将割路径应用于安全路径和多重安全路径的表征，这一应用是由生物信息学中的基因组组装问题激发的。安全路径是出现在每个节点覆盖路径中的子路径。作者证明，一个路径是安全的当且仅当它不是交错的，或者它的核心是一条割路径，这提供了一种比先前方法更简单的线性时间验证方法。对于多重安全路径，它们必须出现在每个节点覆盖集合的某个路径中，作者证明，如果路径是安全的并且剩余结构的一个组件包含一个单节点强连通组件，则该路径是多重安全的。

这项工作改进了这两种路径类型的算法结果。安全路径可以在O(mn)时间内枚举，多重安全路径可以在O(mn)时间内识别并在O(mn + o)时间内枚举，其中o是输出大小。之前的最佳多重安全路径算法运行时间为O(m2 + n3 log n)，因此这是一个显著的改进。这一改进利用了关于剩余结构在子路径扩展或缩短时单调变化的关键观察结果，从而有效地分摊了计算成本。

本文还提出了包括受限可达性、弧瓶颈和路径转换属性在内的广泛技术机制。使用先前关于强连通性查询的预处理技术，在算法执行期间实现了高效的常数时间检查。

总体而言，本文通过严格发展割路径框架、建立基本界限以及展示在计算生物学问题中的实际应用，做出了重要的理论贡献。剩余结构概念及其属性为分析有向图中的连通性提供了灵活的基础。

此内容由AI生成。了解更多