在图中查找最短 "k stride"路径的算法

Question

该图是未加权且无向的。

给定两个顶点 s 和 t，步幅为 k，我想找到它们之间的最短路径:

1. 长度能被k整除

2. 路径中的每 k 个“步骤”，从第一个开始算起，都是一条简单路径。

意思是，每一步只能“跳转”k个顶点(正好是k)的最短非简单路径，而且每一次“跳转”都必须是一个简单的子路径。

我认为这个问题等同于构造第二个图 G'，如果 G 中存在长度为 k 的路径，其中 (u, v) 是 G' 中的一条边，因为 BFS 扫描会给出所需的路径-- 但我没能在合理的时间内构造出这样的图(显然这是一个 NP 问题)。有替代算法吗？

Answer 1

您所描述的问题总体上是 NP 难的，因为您可以将哈密顿路径问题简化为它。具体来说，给定一个 n 节点图和一对节点 s 和 t，您可以通过检查从 s 到 t 的最短 (n-1) 步长路径的长度是否正好为 n 来确定是否存在从 s 到 t 的哈密顿路径-1，因为在那种情况下，有一条从 s 到 t 的简单路径只通过每个节点一次且恰好一次。因此，如果允许 k 相对于 n 较大，则您不应期望有一种特别有效的算法来解决此问题。

如果有帮助，有一些快速算法可以在图中找到长的简单路径，这些算法对于合理的 k 值可能非常有效。查找 color-coding technique ，特别是作为这方面的一个例子。