计算有向图中两个节点之间的简单路径数量有多难？

Question

有一种简单的多项式算法来决定有向图中的两个节点之间是否存在路径（只需使用深度优先搜索的常规图形遍历）即可。

但是，似乎令人惊讶的是，如果我们想要的存在，而不是测试我们想要的存在，那么问题就会变得更加困难 数数 路径数。

如果我们允许路径重复使用顶点，则有一个动态编程解决方案，可以从 s 至 t 和 n 边缘。 但是，如果我们只允许简单的路径（不重用顶点），我能想到的唯一解决方案是路径的蛮力枚举, ，具有指数时间复杂的东西。

所以我问，

• 计算两个顶点之间的简单路径数量吗？
• 如果是这样，它是NP完整的吗？ （我说有点是因为从技术上讲这不是决策问题...）
• P中还有其他问题也有类似的计算版本吗？**

Answer 1

与计数问题相关的最常见的复杂性类是 #P. 。确定从给定节点到另一个节点的简单路径显然在NP中。然后计算它们在#P中。

关于NP的完整性：即使这不是决策问题，它也几乎不适合NP： $ n！$ 路径和非确定性无济于事（您仍然需要检查它们）

您两个前两个问题的答案是：是的，很难， 它是＃p-complete（参考）.

维基百科 文章 给出相关的事实：1）概率算法可用于近似＃p-Complete函数，这就是上一篇文章中用于近似值的算法。 2）硬计数版本还有其他简单问题：

• 查找（线性）与计算所有满足的作业 DNF公式 或一个实例 2-sat
• 查找（线性）与计数拓扑排序
• 查找（o（ve））与计数在两部分图中的完美匹配

您已经知道，如果您删除了“简单路径”问题，则问题落入P（嗯，您必须通过图形大小的多项式绑定路径的长度，或者在Unary中绑定界限）