2
$\begingroup$

I am facing the similar problem to max flow in multiple source-destination directed graph (which has a familiar solution of connecting all the sources to one source and the same for the destination, and solving it with some algorithms like Ford-Fulkerson), but the difference in my problem is that :

  1. all edges has capacity of 1 (the flow is discrete so once an edge is used - it can't be used again)
  2. each source need to flow to a specific destination (e.g. $v_1$ needs to flow to sink $u_1$ - other sinks can't consume $v_1$ flow).

I need to find the max sources that can reach to their destination on a given graph. Is there a solution for this or I have to compute all the possiblities ?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It is subtly implied by the question text, but you should probably explicitly state your flow can only take values in $\{ 0,1 \}$ (and not, for example, non-integer values such as $\frac{1}{3}$). Also, must each source have a flow to a unique destination or is it allowed for flow from a single source to be pumped to multiple sinks? In the former case, what you describe is similar to finding edge-disjoint paths as, for example, it is done in the setting of Menger's theorem. $\endgroup$ – dkaeae Mar 6 '19 at 16:25
  • $\begingroup$ @dkaeae - Edge values can be only 1 or 0. Each source have to flow to a unique destination. You mentioned that it can be done with Menger's theorem. Can you explain how ? $\endgroup$ – yehudahs Mar 12 '19 at 10:28
1
$\begingroup$

This is an instance of a multi-commodity flow problem. Unfortunately the problem is NP-hard (even when all edge capacities are 1).

Improve this answer
$\endgroup$

Your Answer

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

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