algorithmsgraph theory
Given a graph $G=(V,E)$ and $2$ vertices $s,t \in V$, how can I find the maximum number of edge-disjoint paths from $s$ to $t$ using a flow network? $2$ paths are edge disjoint if they don't have any common edge, though they may share some common vertices.
Thank you.
Garey and Johnson, page 214, $K$th Shortest Path:
Given a graph $G=(V,E)$, a positive integer length for each edge, specified vertices $s,t$, and positive integers $B,K$, the question whether there are $K$ or more distinct simple paths from $s$ to $t$ each of length $B$ or less, is not even known to be in NP.
This doesn't quite answer your question, since it does not require the paths to be vertex-disjoint, but it may show you where to start looking.
See also page 217, Maximum Length-Bounded Disjoint Paths: given a graph, two specified vertices, and two positive integers $J,K$, does the graph have $J$ or more mutually vertex-disjoint paths joining the vertices, none involving more than $K$ edges. This one is NP-complete, and actually looks more relevant than the first one.
The answers to the question you linked are not all correct. In particular, the answer relating to maximum flow computation is wrong. Let me first give you an example showing that this answer is wrong and then further readings stating correct algorithms for finding edge-disjoint trees in a graph.
Consider the following graph:
This graph obviously admits a flow of value 2 between any two vertices. However, it does not admit 2 edge-disjoint spanning trees. Assume such two trees $T_1$ and $T_2$ would exist.
Thus, the given graph fulfills the requirement that between every two vertices there exists a flow of value at least two, but the graph does not admit two edge-disjoint trees.
Luckily, another answer to the question you linked is correct: The works of Tutte [1] and Nash-Williams [2] give characterizations of the graphs that admit $k$ edge-disjoint trees as well as algorithms computing these trees.
In the above example, consider the partition $P = \{\{1\}, \{2,6\}, \{3,7\}, \{4\}, \{5\}, \{8\}\}$ for $r = 6$. There are 8 edges with endpoints in different sets of the partition. However, the characterization of Tutte and Nash-Williams requires there to be $k (r - 1) = 2 \cdot 5 = 10$ such edges. Therefore, the above example does not fulfill the conditions.
Since the author of the original answer only gave the authors of the papers, here are the full references to the two papers.
[1] On the Problem of Decomposing a Graph into n Connected Factors, Tutte, 1961, Journal of the London Mathematical Society s1-36(1), pages 221-230
[2] Edge-Disjoint Spanning Trees of Finite Graphs, Nash-Williams, 1961, Journal of the London Mathematical Society s1-36(1), pages 445-450
Best Answer
Hint: if each edge has a capacity of one unit, different units of stuff flowing from $s$ to $t$ must go on edge-disjoint paths.