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.

  • $\begingroup$ 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. $\endgroup$ – Brendan McKay May 12 '12 at 16:38
  • $\begingroup$ Thanks Brendan. From the application point it would be actually quite natural to add the assumption that the network is acyclic. $\endgroup$ – 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

\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.