循环有向图中的最长路径，其边具有限制的传递次数

Question

我有一个带循环的有向图。关于这个图最重要的部分是每条边都有它可以通过多少次的限制，之后它应该变得“不可用”。

我将如何找到最长的路径？任何信息或 link 或评论将不胜感激。谢谢！

Answer 1

不幸的是，这个问题是 NP-complete，这意味着不太可能存在“快速”算法（可以在多项式时间内解决每个实例的算法）；您需要满足于不能保证找到最佳解决方案的快速启发式算法，或者使用只能在合理时间内解决小实例的指数时间算法。

我将通过将 NP 完全问题 Hamiltonian Path in a Directed Graph (HP) 简化为您的问题来展示这一点。简而言之，这个想法是：如果 存在某种算法可以“快速”解决问题的每个实例（意味着在多项式时间内），那么它也可以用作解决每个实例的子例程HP——这似乎不太可能，因为尽管进行了数十年的 CS 研究，但没有人知道如何在多项式时间内解决 HP（或任何 NP 完全问题）。

在HP中，给定一个有向图G = (V, E)，任务是判断是否存在访问所有|V|的路径顶点正好一次。给定这个问题的一个实例，我们可以构造一个你的问题的实例 G'，如下所示：

• 将每个顶点 v 替换为三个顶点 v_in、v_mid 和 v_out，将 v 的所有入边更改为 v_in 的入边，以及将来自 v 的所有出边更改为来自 v_out 的出边；称这些边为“乌木边”（它们对应于 G 中的 edges）。还添加从 v_in 到 v_mid 和从 v_mid 到 v_out 的边；称这些边为“天鹅绒边”（它们对应于 G 中的 顶点）。
• 为每条边指定通过限制 1。

当且仅当原始图G中存在哈密顿路径时，此图中存在长度为3|V|-1的路径：

"If"方向：假设G包含一条哈密顿路径。这对应于构建图中长度为 3|V|-1 的路径，该路径以一对天鹅绒边缘开始和结束，并以 VVEVVE...EVV 模式在天鹅绒边缘和乌木边缘之间交替。

"Only if" direction:假设构造的图中存在一条长度为3|V|-1的路径P。每条边的通过限制为 1，因此每条边在此路径中最多出现一次。 P 必须具有以下边缘模式之一：

1. VVEVVE...EVV
2. VEVVE...EVVE
3. EVVE...EVVEV

在每种情况下，P 至少遍历对应于 G 中每个顶点的两条天鹅绒边中的一条，因此对应于 G 中的哈密顿路径。