# optimal flow for index multiple source and destination in directed graph

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 ?

• 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. – dkaeae Mar 6 at 16:25
• @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 ? – yehudahs Mar 12 at 10:28