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 ...
- 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 (...
- 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 ...
- 166
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.)
...
- 11.7k
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 ...
- 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 ...
- 9,595
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 ...
- 9,595
Only top scored, non community-wiki answers of a minimum length are eligible