Search code examples
algorithmpathnpcover

Find the maximum vertex-disjoint path cover

Suppose I have a directed graph with weights on each node. The weight of a path between any two nodes is defined as the following: sum of all nodes in the path and multiply by the number of nodes in that path.

We want to find a vertex-disjoint path cover that has the maximum sum of weights of all the paths in that cover.

I know this is a NP problem. Is there any algorithm that solve this problem? Or is there any problem that reduce to this problem?

Solution

  • There's an O(3^n poly(n))-time algorithm. The steps are

    1. Find all sets of vertices that can be arranged in a path.
    2. Solve the resulting set packing problem.

    Step 1 is accomplished by a dynamic program whose table is indexed by pairs consisting of (a) the set of vertices in the path (b) the first vertex in the path. Step 2 is also accomplished by a dynamic program, with a table mapping sets of vertices to the maximum value attainable by disjoint paths on that subgraph.

    The recurrence for Step 1 is

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

    Now gather all sets P such that there exists v in P such that IsPath(P, v). Compute the score for each of these paths.

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