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