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.

  • 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 Dec 11 '17 at 1:02
  • 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 Jun 23 at 13:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.