I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather different so i need an advice.

Suppose that we have a weighted directed graph with two (possibly the same) vertices designated as "source" (S) and "target" (T). We can imagine that vertices represent the currencies and edges are conversion options. There is some initial amount of money in vertex S and it has to be converted to vertex T in such way that the resulting sum is maximum possible.

Conversion can be done in parts so if there is some sum S at vertex V and there are several edges coming from V then we can send different amounts of money along these edges (i.e. we are not obliged to use only one edge or to divide the sum in equal parts or to use multiples of some fixed lot etc.). We are also not obliged to convert total sum. It can be the case that the best option is to convert some part of it.

Now comes the trickiest part. Each edge's weight depends on amount of money that must be transported through an edge. For each edge E there is some function F(E) that receives amount of money entering the edge and returns amount of money leaving the edge. We can assume that ratio of output/input gets smaller when input gets bigger.

Thank you very much for any ideas. Any help will be highly appreciated.

  • $\begingroup$ How are the functions $f$ specified? In other words, how are they provided as input? Are they totally arbitrary? I'd expect this to be computationally hard if the functions $f$ can be arbitrary (this is just speculation). Do you want to know the the theoretical worst-case running time, or are you looking for a practical solution? If the latter, how large is the problem? About how many vertices and edges do you expect and how large is the initial sum (very roughly)? $\endgroup$
    – D.W.
    Jul 6, 2018 at 15:06
  • $\begingroup$ @D.W. Thanks for your comment. I'm looking for a practical and probably suboptimal solution. Functions are arbitrary, there are no special requirements imposed on them. Size of the problem: there are no more than N=100 vertices but number of edges can be up to N^2 $\endgroup$
    – Igor
    Jul 9, 2018 at 8:32

1 Answer 1


Your problem is a generalization of the Longest Path problem, which is NP-hard. If the functions are constant and every conversion increases the amount of money, then there's no reason not to convert all of the money at once. At that point, you are just looking for the longest path.

Your generalization, allowing partial conversions, non-constant functions, etc. cannot be easier than that.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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