Tag Info

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

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

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.) ...
• 12.2k
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
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 ...