Covering max flow arcs by arc disjoint paths

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.

• It isn't true for any maximal flow. For example, to your example add an unreachable cycle of capacity $T$ and put a flow of magnitude $T$ around it. However, it might be true of acyclic maximal flows. If not, it still might be true of flows that can be constructed by augmenting paths. – Brendan McKay May 12 '12 at 16:38
• Thanks Brendan. From the application point it would be actually quite natural to add the assumption that the network is acyclic. – Thomas Kalinowski May 12 '12 at 22:55

It looks like the following argument works. Consider a binary program to maximize $\sum_{a\in A^*}\xi_a$ subject to the constraints
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.$$