1
$\begingroup$

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.

$\endgroup$
2
  • $\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$ May 12, 2012 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$ May 12, 2012 at 22:55

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .