Editing Maximum flow problem (section)

===Maximum number of paths from s to t===
Given a directed graph <math>G = (V, E)</math> and two vertices <math>s</math> and <math>t</math>, we are to find the maximum number of paths from <math>s</math> to <math>t</math>. This problem has several variants:

1. The paths must be edge-disjoint. This problem can be transformed to a maximum flow problem by constructing a network <math>N = (V, E)</math> from <math>G</math>, with <math>s</math> and <math>t</math> being the source and the sink of <math>N</math> respectively, and assigning each edge a capacity of <math>1</math>. In this network, the maximum flow is <math>k</math> iff there are <math>k</math> edge-disjoint paths.

2. The paths must be independent, i.e., vertex-disjoint (except for <math>s</math> and <math>t</math>). We can construct a network <math>N = (V, E)</math> from <math>G</math> with vertex capacities, where the capacities of all vertices and all edges are <math>1</math>. Then the value of the maximum flow is equal to the maximum number of independent paths from <math>s</math> to <math>t</math>.

3. In addition to the paths being edge-disjoint and/or vertex disjoint, the paths also have a length constraint: we count only paths whose length is exactly <math>k</math>, or at most <math>k</math>. Most variants of this problem are NP-complete, except for small values of <math>k</math>.<ref>{{Cite journal|last1=Itai|first1=A.|last2=Perl|first2=Y.|last3=Shiloach|first3=Y.|year=1982|title=The complexity of finding maximum disjoint paths with length constraints|journal=Networks|language=en|volume=12|issue=3|pages=277–286|doi=10.1002/net.3230120306|issn=1097-0037}}</ref>