# Minimum weight $k-$path cover on a DAG proof verification

Suppose you are given a directed acyclic graph $$G$$ with $$n$$ vertices and an integer $$k \leq n$$. Each edge has an associated weight $$w(u,v)$$. We want to find $$k-$$vertex-disjoint paths that cover all vertices of the graph such that it minimizes the total sum of the weights of all edges in the paths. (assume such $$k-$$ path cover exists).

I am trying to design an $$O(n^{k+3})$$ dynamic program for the problem. Namely, fix a topological sort $$u_1, ..., u_n$$ of the DAG vertices. Let $$dp(v_1, ..., v_k, i)$$ denote the minimum total sum of weights of a $$k-$$path-cover starting at vertices $$v_1, ..., v_k$$, and covering vertices $$u_{i}, ..., u_n$$. Then we have the recurrence:

$$dp(v_1, ..., v_k, i) = \min_{j : (v_j,u_i) \in E}\{w(v_j, u_i)+dp(v_1, ..., v_{j-1}, u_i, v_{j+1}, ..., v_k, i+1)\}$$

if $$\exists v_j : (v_j, u_i)\in E$$ and $$\infty$$ if not. (I am skipping the base cases here for $$i=n$$ as it is trivial to handle).

The recurrence just means that path $$j$$ is extended from ending at $$v_j$$ to now end at $$u_i$$. The crucial thing to note is that $$u_i$$ does not point to any vertex from $$u_1, ..., u_{i-1}$$ as that would contradict the topological sort order, which ensures that the path built by the DP is vertex disjoint.

The final solution to the problem is simply $$\displaystyle dp(\phi, \phi, ..., \phi, 1)$$ where $$\phi$$ is a virtual vertex that is connected to all vertices of $$G$$ with cost $$0$$. This DP has $$O((n+1)^{k}n)=O(n^{k+2})$$ states, and each state takes $$O(n)$$ time to compute.

Does this solution sound right? My main concern is if the paths generated by the DP are vertex disjoint.

• The way to know whether the paths are vertex disjoint is to prove that they will be. What attempts have you made to prove this or search for a counterexample? What progress have you made?
– D.W.
Commented Jul 19, 2021 at 5:21
• @D.W. I can now prove that the algorithm returns the minimum weight of paths that are vertex disjoint and concatenation of the topological sort I fixed (because each vertex is assigned to exactly one path if $dp$ is finite). I can also prove that for optimal paths $P_1^\ast, ..., P_k^\ast$, it can be generated by concatenation and inserting vertices in the order of the topological sort that I fixed. This should be sufficient to prove that the generated paths have minimum weight since the $dp$ value is precisely the total weight of the paths. Commented Jul 19, 2021 at 7:42