Let $(N,A,s,t,u)$ be a network with node set $N$, arc set $A$, source $s\in N$, sink $t\in N$ and capacity vector $u\in\{1,2,\ldots,T\}^A$, and let $x=(x\_a)\_{a\in A}$ be a maximum $(s,t)$-flow. Is it always possible to find a collection of arc disjoint, flow-carrying $s$-$t$-paths that cover all arcs $a$ with flow $x\_a=T$?


This question came up in work on the scheduling of arc outages to maximize the total flow over a time horizon. 


 **Update:**  To avoid Brendan's counterexample let's assume that every node can be reached from the source $s$, and from every node the sink $t$ can be reached. Fixing a flow $x$ we can reduce the capacity of every arc to its flow value (and delete zero capacity arcs) without really changing the problem. Now the question is as follows:



>  Given a network with the property that for every node $v\in N\setminus\{s,t\}$ the sum of the capacities of the incoming arcs equals the sum of the capacities of the outgoing arcs, can the arcs of maximum capacity be covered by a collection of arc-disjoint $s$-$t$-paths?


In this formulation it seems possible that someone has looked at this problem before.



Covering max flow arcs by arc disjoint paths
It looks like the following argument works. Consider a binary program to maximize $\sum\_{a\in A^\*}\xi\_a$ subject to the constraints


\begin{align} 
\sum\_{a\in\delta^+(v)}\xi\_a-\sum\_{a\in\delta^-(v)}\xi\_a &=0 &&\text{for }v\in V\setminus\{s,t\},\\\\ 
\xi\_a&\in\{0,1\} && \text{for }a\in A.
\end{align}


where $A^\*=\{a\in A\ :\ x\_a=T\}$ is the set of arcs that have to be covered, and $\delta^+(v)$ and $\delta^-(v)$ are the sets of outgoing and incoming arcs of node $v$, respectively. The desired covering exists if and only if the optimal objective value for this problem is $\lvert A^\*\rvert$. The constraint matrix is totally unimodular, so we don't lose anything by relaxing the integrality constraint to $0\leqslant \xi\_a\leqslant 1$. It is sufficient to show that $\lvert A^\*\rvert$ is a lower bound for the dual problem which is to minimize $\sum\_{a\in A}\eta\_A$ subject to
\begin{align}
\pi\_{v}-\pi\_w+\eta\_a &\geqslant 0 && a=(v,w)\in A\setminus A^\*, &&(1)\\\\
 \pi\_{v}-\pi\_w+\eta\_a &\geqslant 1 && a=(v,w)\in A^\*,&&(2)\\\\
\pi\_s=\pi\_t&=0,\\\\
\eta\_a &\geqslant 0 && a\in A.
\end{align}


The given flow $x=(x\_a)\_{a\in A}$ can be decomposed into $s$-$t$-paths such that arc $a$ is on exactly $x\_a$ paths. Let $\mathcal P$ be the set of paths in a fixed decomposition. Now adding constraints (1) and (2) along any path $P\in\mathcal P$ gives $\sum\_{a\in P}\eta\_a\geqslant\lvert P\cap A^\*\rvert$. Summing over all paths $P\in\mathcal P$ we obtain $\sum\_{a\in A}x\_a\eta\_a\geqslant T\lvert A^\*\rvert$, and finally,
$$\sum\_{a\in A}\eta\_a\geqslant\sum\_{a\in A}\frac{x\_a}{T}\eta\_a\geqslant\lvert A^\*\rvert.$$


I find the argument a bit unsatisfying as it does not provide a combinatorial algorithm for finding the required paths.


