Let's consider a weighted graph $G = (V,E)$ not directed. In this graph, there are several sinks $S$, which are vertices.

Let's consider one vertex $V$ of this graph (which is a source). The problem is twofold:
- Can we compute the maximum number of vertex-disjoint paths $M_{max}$ given a constraint on the cost $C_{max}$ and the number of edges $E_{max}$? If yes how?
- Can we get the $N$ sets of vertex-disjoint paths (with $1$ to $M_{max}$ paths in each set)? If yes how?

I'm quite novice in the graph theory field, I just have experience with Dijkstra, which is a sub-problem of the minimum-cost flow problem, itself being a sub-problem of the multicommodity flow problem. It seems to me the problem exposed here is a minimum cost multi-commodity flow problem with only $1$ source and the $2$ constraints exposed above. I might be wrong. Could you direct me in the right direction to solve this problem? I did not see any question in math.SE adressing the multi-sink issue, while there are answers for a mono-source/mono-sink issue here or here.

The best thing would be if you direct me towards a library that solves this kind of problem :)

  • $\begingroup$ Just collapse all of the sinks into one node, which becomes your new mono-sink. Similarly for the two ends of your source. $\endgroup$ – Henning Makholm May 18 '16 at 16:04
  • $\begingroup$ Thanks for the answer (and also to Christmas elves editors). I understand the principles of the collapsing. I don't understand how my source has two 'ends' however, my graph being not directed. $\endgroup$ – WebRoamer May 19 '16 at 13:15
  • $\begingroup$ x @WebStroller: Didn't you say your source was an edge? Edges have two ends, yes? $\endgroup$ – Henning Makholm May 19 '16 at 13:23
  • $\begingroup$ Yes, complete inversion of my part on vertices & edges notions. I warned that I was a novice, but still I'm very sorry. So, the problem is vertex-disjoint paths. The source is a vertex, as well as sinks. I'm going to edit the problem. I think the solution is similar though: I collapse my (vertices) sinks into one and use the solutions already proposed in my question. I think I saw something on the constraint on the maximum number of edges Emax. If someone know how to deal with the constraint, I'll be happy to have it, otherwise, I'll edit this answer with the appropriate link. $\endgroup$ – WebRoamer May 19 '16 at 13:37
  • $\begingroup$ I achieved the 'Maximum number of vertex-disjoint path' problem, which is indeed pretty straightforward: 1. create the dual edge-disjoint problem version of the graph (explained in links in the OP) 2. Collapse all sinks into one as mentioned by @Henning Makholm 3. Use a max-flow algorithm which will give you the desired value for each node. However, this does not answer the original problem. Gerry Myerson gives a good reference in another question. $\endgroup$ – WebRoamer May 27 '16 at 13:17

Your Answer

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

Browse other questions tagged or ask your own question.