Network flows with capacities on pairs of edges

2012-05-24T14:54:29Z

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.

Now add edge-pair capacities: for each pair of edges, there is some maximum total flow for those two edges.

This new problem is solvable in polynomial time since it is a linear program, but I don't want to use such a sledge-hammer.

Is there a way to convert this problem into an at-most-polynomially-larger ordinary network flow problem?
Can it be solved using an augmenting-flow type of approach?
In the original problem, if the capacities are integers then there is an optimum flow which is integer. This is not true in the new problem, but is it true that there is an optimum flow in which the edge flows are integer or half integer?
The polytope of all flows is interesting in the original problem; is it still interesting in the new problem? (Choose your own definition of "interesting".)

UPDATE: Q3 was answered in the negative by Douglas Zare. Let me now weaken the hypothesis. Say that a pair-capacity $c(e_1,e_2)$ bites if $c(e_1,e_2)\lt c(e_1)+c(e_2)$. What happens in Q3 if no two biting pair-capacities have an edge in common? [Also negative per Douglas.]

Answer by Douglas Zare for Network flows with capacities on pairs of edges

2012-05-25T01:23:09Z

Here is a simple counterexample to 3. Let the vertices be $\lbrace s, v, t\rbrace$. Let there be two edges $e_1$ and $e_2$ from $s$ to $v$, and one edge $e_3$ from $v$ to $t$.

$$s \overset{e_1}{\underset{e_2} \rightrightarrows} v \overset{e_3} \rightarrow t$$

Let the conditions be $c(e_1,e_3) \le 1, c(e_2,e_3) \le1$. There is a flow of size $2/3$ possible by letting $1/3$ flow through $e_1$ and $e_2$ and letting $2/3$ flow through $e_3$. There is no way to have a flow of size $1$, so there is no integer or half-integer flow which is at least as large as $2/3$.

The same idea works on a larger graph without a doubled edge.

Update: A slight modification of this counterexample has no intersecting biting pairs.

$$s \overset{e_1}{\underset{e_2} \rightrightarrows} v \overset{e_3} \rightarrow w \overset{e_4} \rightarrow t$$

Then $c(e_1,e_3) \le 1, c(e_2,e_4) \le 1$ has the same effect as in the previous example, and the maximum flow is also $2/3$.

Network flows with capacities on pairs of edges - MathOverflow

Network flows with capacities on pairs of edges

Answer by Douglas Zare for Network flows with capacities on pairs of edges