0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Commented Jul 19, 2021 at 5:21
  • $\begingroup$ @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. $\endgroup$ Commented Jul 19, 2021 at 7:42
  • $\begingroup$ Have you answered your own question? If so, I encourage you to answer your own in the question in the space for an answer below. $\endgroup$
    – D.W.
    Commented Jul 19, 2021 at 16:29

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.