Covering max flow arcs by arc disjoint paths

Question

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.

Answer 1

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.