17 votes
Accepted

Counterexample to max-flow algorithms with irrational weights?

The answer is that for every irrational number $r$, there exists a network with $n=6$ vertices and $m=8$ arcs, in which seven arcs have integer capacity, in which one arc has capacity $r$, and on ...
Gamow's user avatar
  • 5,772
6 votes

All-or-Nothing Single-Sink Flow Problem

While I can't give you a name, I can provide evidence that the problem is $\mathbf{NP}$-hard to approximate to any factor, and thus is likely to be unstudied in full generality in the literature (...
Yonatan N's user avatar
  • 1,642
5 votes
Accepted

Maximum flow with parity requirement on certain edges

We can construct a widget for an all-or-nothing flow of capacity 4 from vertex s to t using the widget below. The stars (*) indicate even flows. By recursively applying similar widgets one can emulate ...
Albert Hendriks's user avatar
3 votes

Max flow with restriction of individual flows

That constraint is linear, so the entire problem is an instance of linear programming, thus can be solved in polynomial time. (I am assuming there is no restriction or requirement for integer flows.) ...
D.W.'s user avatar
  • 12k
3 votes
Accepted

Max network flow with arbitrary source / sink

Finding max flow from arbitrary source/sink can be reduced to finding max flow under insertion/deletion of edges. We modify the graph by adding two vertices $s^*$ and $t^*$ not connected to any ...
sbzk's user avatar
  • 171
2 votes

Maximum flow with parity requirement on certain edges

Theorem 1. The problem is NP-hard. Proof sketch. By reduction from maximum independent set in cubic graphs (which is NP-hard). Given a cubic graph $G=(V, E)$, the reduction outputs a flow network as ...
Neal Young's user avatar
  • 10.1k
2 votes

Max flow with restriction of individual flows

Lemma 1. The problem (assuming integer flow is required) is NP-hard. Proof sketch. The proof is by reduction from 3D-matching. The reduction is similar to the reduction for equal flow referred to ...
Neal Young's user avatar
  • 10.1k

Only top scored, non community-wiki answers of a minimum length are eligible