Dynamic programming for graph splitting

Question

I have a directed graph which has edges between every vertices $i$ and $j$ such that $i < j$ and the edge is from i->j and every vertex needs to be visited. I need to divide the graph into two parts such that the travel distance on both the parts i.e. sum of edge weights while traveling from the lowest index to the highest index in each of the group is minimum. For example there is a graph of 4 vertices where each edge weight is the following

• $w(1, 3) = 2$
• $w(1, 4) = 1$
• $w(3, 4) = 3$
• $w(1, 2) = 100$
• $w(2, 3) = 100$
• $w(2, 4) = 100$

The solution would be $\{2\}, \{1, 3, 4\}$. In the first group {2} doesn't have any vertex so no edges between any of the vertices in that group. In the second group we travel from 1->3 and 3->4 so the edges we travelled would be 2 + 3. Hence the ans would be 0 (from the first group) + (2+3) (from the second group). We start from the lowest index vertex and move to the highest index vertex as the edges are from lower index to higher index vertex.

The algorithm I came up was a brute force i.e. considering each combination and return the minimum of it i.e. to take one vertex in one group or include in other which leads to complexity $O(2^n)$.

I want to get the above problem to run in $O(n^2)$ solution. I did draw a decision tree for the above problem and can see nodes being overlapped i.e. $\{1,2\}, \{3,4\}$ and $\{3,4\}, \{1,2\}$ so I figured this is a dynamic programming problem but I am not able to define the states.

Edit - It can be done using a 1d dp array

Answer 1

I don't have a dynamic programming solution but this problem can be efficiently reduced to a minimum weight max-flow problem.

Let $G$ denote your original graph. We will create an instance $(s,t,G')$ of the minimum weight max-flow problem as follows:

• Let $W$ denote the sum of all weights in $G$ plus one.
• For every vertex $u$ in $G$, we create two vertices $u_{in}$ and $u_{out}$ in $G'$ and add a directed edge from $u_{in}$ to $u_{out}$ with weight $-W$ and capacity $1$.
• For every directed edge $e=(u,v)$ in $G$, we add a directed edge from $u_{out}$ to $v_{in}$ in $G'$ with weight $w(e)$ and capacity $1$.
• We create a vertex $s'$ and we connect the source $s$ to $s'$ with a directed edge of weight $0$ and capacity $2$.
• We connect $s'$ to every "in" vertex with a directed edge of weight $0$ and capacity $1$. We connect every "out" vertex to the sink $t$ with a directed edge of weight $0$ and capacity $1$.

Let $n$ denote the number of vertices in $G$. Then the vertices in $G$ can be partitioned into two vertex-disjoint paths of total weight $k$ (which is what you want) if and only if there is a max-flow in $(s,t,G')$ with total weight $k-nW$. Moreover, this flow is the union of two paths in $G'$ (which are disjoint except at $s$, $s'$ and $t$) , from which you can easily retrieve the two vertex-disjoint paths in $G$.

Note that by changing the capacity of the $(s,s')$ edge from $2$ to whatever integer we like, we can generalize this approach to partitioning into arbitrary number of vertex disjoint paths with minimum total weight.