1
$\begingroup$

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

$\endgroup$
16
  • 1
    $\begingroup$ It sounds like a min-cut problem. Can you formally define your problem? What are you optimizing over? You want to partition the graph into two parts, A and B such that the weight of the edges with one endpoint in A and one endpoint in B is minimized? $\endgroup$ – Pål GD Mar 5 at 11:13
  • $\begingroup$ "such that the sum of the weight of the edges traveling from the lowest index to the highest index is minimum" -- (1) What does "travelling from" mean? There could be multiple paths from the lowest-index vertex to the highest. (2) How does the division into two parts affect this travelling? It doesn't appear to at all from your current description. $\endgroup$ – j_random_hacker Mar 5 at 13:55
  • $\begingroup$ @PålGD, yes you are correct for each part I need to travel from the minimum endpoint to the maximum endpoint as the edges are between i and j such that i < j. eg - 1-2 , 2-3, 1-3 and so on. When we travel from one endpoint to the other endpoint in each part we are optimizing the travel distance i.e. the sum of edge weights $\endgroup$ – Vighnesh Kumar Mar 5 at 20:26
  • $\begingroup$ @j_random_hacker 1) Travelling from meaning travelling from vertex i to vertex j as the edges are between i and j such that i < j. eg- 1-2, 2-3 and 1-3 and so on. There won't be multiple paths as it is a directed graph eg - if there I travel from 1->3, then I won't be able to travel the edge 2->3 as the edges will be from the lower index to higher index. $\endgroup$ – Vighnesh Kumar Mar 5 at 20:26
  • 1
    $\begingroup$ @VighneshKumar. In your example you say that the optimal cost is $5$. In the comment you say that the cost is the sum of the weights $(i,j)$ with $i<j$ and $i,j$ in the same group. This would give cost of $6$. Then in the next comment you again only consider edges $(1,3)$ and $(3,4)$ ignoring edge $(1,4)$. Can you please formally define the measure that you want to minimize? $\endgroup$ – Steven Mar 5 at 21:27
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ What should be the value of k? $\endgroup$ – Vighnesh Kumar Mar 6 at 0:04
  • $\begingroup$ You don't need to choose $k$, $k-nW$ is the value given by the min-cost max-flow algorithm. $\endgroup$ – Tassle Mar 6 at 0:11
  • $\begingroup$ Understood but I don't think this solution will run within O(n^2) time $\endgroup$ – Vighnesh Kumar Mar 6 at 0:20
  • $\begingroup$ @VighneshKumar You are right, it will be more like $O(n^5)$ here. But that's still a big improvement over $O(2^n)$! $\endgroup$ – Tassle Mar 6 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.