Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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.... –  Suvrit May 25 '12 at 4:29
add comment

1 Answer

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

share|improve this answer
    
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. –  Brendan McKay May 25 '12 at 3:04
    
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 ;). –  Brendan McKay May 25 '12 at 3:49
    
I don't know how to eliminate this phenomenon. I think this counterexample is interesting because it restricts the possibilities for problem 1. –  Douglas Zare May 25 '12 at 3:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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