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.

  1. Is there a way to convert this problem into an at-most-polynomially-larger ordinary network flow problem?
  2. Can it be solved using an augmenting-flow type of approach?
  3. 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?
  4. 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.]

  • $\begingroup$ This reminds me a bit about polymatroidal flows, except that in your case the "pair" of edges can be arbitrary, not necessarily incident on the same vertex. Perhaps some "fractional" version of this exists.... $\endgroup$
    – Suvrit
    May 25, 2012 at 4:29

1 Answer 1


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

  • $\begingroup$ Great! That indeed answers Q3. The 2/3 flow is clearly optimal, and the same idea shows that any denominator is possible in an optimal flow. $\endgroup$ May 25, 2012 at 3:04
  • $\begingroup$ On the update: Um, yes, I should have thought longer before adding that update. But somehow your example is really the same as before; maybe you can suggest the additional condition I need ;). $\endgroup$ May 25, 2012 at 3:49
  • $\begingroup$ I don't know how to eliminate this phenomenon. I think this counterexample is interesting because it restricts the possibilities for problem 1. $\endgroup$ May 25, 2012 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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