找到最大的顶点不相交路径覆盖

Question

假设我有一个有向图，每个节点都有权重。任意两个节点之间路径的权重定义如下：路径中所有节点的总和乘以该路径中的节点数。

我们想要找到一个顶点不相交的路径覆盖，它具有该覆盖中所有路径的最大权重总和。

我知道这是一个NP问题。有解决这个问题的算法吗？或者有什么问题可以减少到这个问题？

Answer 1

有一个时间复杂度为 O(3^n poly(n)) 的算法。步骤为

1. 找到可以排列在路径中的所有顶点集。
2. 解决结果集打包问题。

第 1 步由动态程序完成，其 table 由以下项组成的对索引：(a) 路径中的顶点集 (b) 路径中的第一个顶点。第 2 步也是通过动态程序完成的，其中 table 将顶点集映射到该子图上不相交路径可获得的最大值。

第 1 步的重复次数是

IsPath({v}, v) = true (for all vertices v)
IsPath(S, v) = exists w in S - {v} such that v->w is an arc and IsPath(S - {v}, w) (for all sets of vertices S, for all v in S).

现在收集所有集合 P 使得 P 中存在 v 使得 IsPath(P, v)。计算每条路径的分数。

BestCover({}) = 0
BestCover(S) = max Score(P) + BestCover(S - P) over all P subset of S such that P is a path (for all nonempty S).