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

Question

假设我有一个有向图，每个节点上都有权重。任意两个节点之间的路径权值定义为:该路径上所有节点的和乘以该路径上的节点数。

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

我知道这是个NP问题。有什么算法可以解决这个问题吗?还是有什么问题可以归结为这个问题?

Answer 1

有一个O(3^n) poly(n) time算法。步骤如下

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

步骤1是由一个动态规划完成的，这个动态规划的表是由(a)路径上的顶点集(b)路径上的第一个顶点组成的成对索引的。步骤2也由一个动态程序完成，用一个表将顶点集映射到该子图上不相交路径可达到的最大值。

步骤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).