<p>Suppose we have a weighted DAG $G$. A $m$-path-tuple is defined as $(P_1, ..., P_m)$ in which $P_i$ is a path on the graph, and no $P_i$ and $P_j$ share any edges. In other words each edge of the graph belongs to at most one of these paths. Among these $m$-path-tuples, we want to find the one that has the maximum weight, i.e., sum of the weight of its edges are more than any other $m$-path-tuple. </p>

<p><strong>A max-flow min-cost formulation:</strong>
We connect every vertex without incoming edge to source and every vertex without outgoing edge to sink. Also we set the capacity of every edge edge to 1, and then setting the capacity of the source to $m$. In the end we set the cost of each edge to $-w(e)$ and minimise the cost via a "max-flow-min-cost" method. The $capacity=1$ makes sure the paths won't have any edge in common, while minimising the cost would effectively maximise the total weight. The problem with this approach is that it introduces negative weights and therefore solving it is quite slow. I was wondering if is a better way to solve it given that it's a DAG and not any arbitrary graph. </p>

CC BY-SA 3.0
2017-12-11T01:02:09.353Z
Why are negative weights making things slow? On the top of my head, the min-cost flow algorithms I know handle negative costs without a problem. Also, is $m$ a constant or part of the input?
Chao Xu
CC BY-SA 4.0
2018-06-23T13:27:18.547Z
Your reduction to min-cost flow is not quite correct.  You need to add edges from the source into _every_ vertex, and from _every_ vertex to the sink.  (Otherwise you won't be able to consider all possible paths.  Consider for example if G already has a root vertex v that has an edge into every other vertex...)
Neal Young
<graph-theory><max-flow-min-cut>
Maximum weight non-overlapping paths in a DAG
AmeerJ
# Maximum weight non-overlapping paths in a DAG

(Asked by: username_0 on 2017-12-10)

Suppose we have a weighted DAG $G$. A $m$-path-tuple is defined as $(P\_1, ..., P\_m)$ in which $P\_i$ is a path on the graph, and no $P\_i$ and $P\_j$ share any edges. In other words each edge of the graph belongs to at most one of these paths. Among these $m$-path-tuples, we want to find the one that has the maximum weight, i.e., sum of the weight of its edges are more than any other $m$-path-tuple.

**A max-flow min-cost formulation:**
We connect every vertex without incoming edge to source and every vertex without outgoing edge to sink. Also we set the capacity of every edge edge to 1, and then setting the capacity of the source to $m$. In the end we set the cost of each edge to $-w(e)$ and minimise the cost via a "max-flow-min-cost" method. The $capacity=1$ makes sure the paths won't have any edge in common, while minimising the cost would effectively maximise the total weight. The problem with this approach is that it introduces negative weights and therefore solving it is quite slow. I was wondering if is a better way to solve it given that it's a DAG and not any arbitrary graph.

**Tags:** graph-theory, max-flow-min-cut

> **Comments:**
> **username_1**: Why are negative weights making things slow? On the top of my head, the min-cost flow algorithms I know handle negative costs without a problem. Also, is $m$ a constant or part of the input?  
> **username_2**: Your reduction to min-cost flow is not quite correct.  You need to add edges from the source into _every_ vertex, and from _every_ vertex to the sink.  (Otherwise you won't be able to consider all possible paths.  Consider for example if G already has a root vertex v that has an edge into every other vertex...)  

---

## 0 answers

