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.

  • $\begingroup$ 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? $\endgroup$
    – Chao Xu
    Dec 11, 2017 at 1:02
  • $\begingroup$ 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...) $\endgroup$
    – Neal Young
    Jun 23, 2018 at 13:27


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.