Skip to main content
44 votes

Residual Graph in Maximum Flow

The intuition behing the residual graph in the Maximum flow problem is very well presented in this lecture. The explanation goes as follows. Suppose that we are trying to solve the maximum flow ...
Mario Cervera's user avatar
13 votes
Accepted

How to find max flow in a graph after decrementing an edge capacity?

If the capacity of edge $c(e') \ge f(e') + 1$ i.e. the max flow remains the same, there is no chance max flow increase, as it would increased without decreasing $c(e')$. Suppose that $c(e') = f(e')$ (...
Marcelo Fornet's user avatar
13 votes
Accepted

Minimum-cut with minimum number of edges

Those answers assume that all edge capacities are integers. Assuming they are, this works. Suppose the min-cut in the original graph has total capacity $x$; then it will have total capacity $x(|E|+1)...
D.W.'s user avatar
  • 162k
12 votes

How to find a minimum cut of a network flow?

The minimum cut is a partition of the nodes into two groups. Once you find the max flow, the minimum cut can be found by creating the residual graph, and when traversing this residual network from ...
JimN's user avatar
  • 851
9 votes

Why in Flow network, there is no reversed edges?

Here is your definition of reversed edges in the case of flow network given in your comment. Between 2 vertices there is the normal forward edge (u,v) , and another edge (v,u) that goes backward(...
John L.'s user avatar
  • 39.1k
8 votes

Compute a max-flow from a min-cut

In the worst case, the minimum cut itself doesn't convey much information about the maximum flow. Consider a graph $G=(V,E)$ in which the minimum $s,t$-cut has value $w$. If I extend $G$ by adding a ...
Tom van der Zanden's user avatar
8 votes

In a flow network, is it possible to restrict the flow going into a node?

I believe you can represent node N as two nodes, A and B. Node A has all of the inbound flow edges of N, and Node B has all of the outbound flow edges of N. Nodes A and B are connected by a single ...
Matthew Pope's user avatar
8 votes
Accepted

Ford-Fulkerson vs Edmonds-Karp

Edmonds-Karp is a specialisation/elaboration of Ford-Fulkerson, so any bound for the latter also applies to the former. In other words, EK is $O(|E|\min(f_{max}, |V||E|))$ time (and writing it this ...
j_random_hacker's user avatar
7 votes
Accepted

Allocating flows in a network while avoiding a particular node

Flows with more than one "thing" flowing are known as "multicommodity flows". The basic definitions assume that every thing can flow through every vertex and edge. However, the standard way of ...
David Richerby's user avatar
7 votes
Accepted

Algorithm for solving incremental max flow problem

You can do it in $\small \mathcal{O}(m + n)$ time where $\small m$ and $\small n$ are the # of edges and vertices respectively. Let the edge to be updated be $\small e = (u, v)$. If you increment ...
PSPACEhard's user avatar
7 votes
Accepted

Reducing max flow to bipartite matching?

Strangely enough, no such reduction is known. However, in a recent paper, Madry (FOCS 2013), showed how to reduce maximum flow in unit-capacity graphs to (logarithmically many instances of) maximum $b$...
dwajc's user avatar
  • 86
7 votes

The same outgoing and incoming degree in graph

If such an orientation is possible, then all degrees are even. Conversely, if all degrees are even then the graph is Eulerian. Orient the edges according to an Eulerian circuit.
Yuval Filmus's user avatar
6 votes
Accepted

Set of vertex-disjoint cycles maximizing different colored vertices

It cannot be solved in polynomial time, assuming P$\,\neq\,$NP. Without worrying about colors (i.e. if every vertex had the same color), it is the MAX SIZE EXCHANGE problem from the Kidney Exchange ...
tjhighley's user avatar
  • 507
6 votes
Accepted

Integral solutions to circulation problem

Circulation problems are not just a generalization of max-flow, there is a reduction backwards as well. Suppose we have some directed graph $G = (V, E)$ with edge costs, capacities, and lower bounds. ...
orlp's user avatar
  • 13.6k
6 votes

Find max total revenue in a directed graph

Your problem can be solved by reducing it to a min-cost max-flow problem where a unit of flow represents one unit of commodity. A negative cost represents a profit. Create a directed graph containing $...
Steven's user avatar
  • 29.5k
6 votes

P=NP? A reduction of CNF boolean satisfiability to the circulation problem in an undirected graph

Consider the CNF formula $a \wedge \neg a$. This has two clauses, $a$, and $\neg a$. If I understand your scheme correctly this maps to the following flow problem: This clearly has a solution (1 flow ...
orlp's user avatar
  • 13.6k
5 votes

Improvement of algorithm due to constrained graph

Edmonds-Karp algorithm works by building successive flows $f_0, \dots, f_n$ where each flow $f_{i+1}$ can be obtained by combining $f_i$ and a path in the "residual graph" $G_{f_i}$ obtained through a ...
Louis's user avatar
  • 153
5 votes

New Applications of Network Flow

Network flow has been used for all sorts of interesting and surprising tasks in computer vision and image processing. For instance, it has been used for image segmentation, image stitching, seam ...
D.W.'s user avatar
  • 162k
5 votes
Accepted

Perfect matching in a bipartite regular graph in linear time

There is a classical linear time algorithm of Gabow and Kariv. The first step is to find an Eulerian tour. You do this by starting at an arbitrary vertex and following an arbitrary path until you ...
Yuval Filmus's user avatar
5 votes

Flow graph that requires pushing back flow in Ford Fulkerson

There is a network that forces Ford-Fulkerson to push flow back. Intuition Consider executing Ford-Fulkerson (FF) on any flow network where all edges capacities are at least 2. No matter how FF ...
Neal Young's user avatar
5 votes
Accepted

find the union of all min cuts of a flow network

Note $S_{\max}=V-\bigcap_{S\in\mathcal{F}}(V-S)$. And $\bigcap_{S\in\mathcal{F}}(V-S)$ is the set of all vertices from which $t$ is reachable in the residual graph. The reason why $\bigcap_{S\in\...
xskxzr's user avatar
  • 7,510
4 votes
Accepted

Checking if a given flow is a maximum flow

A flow is maximum if there is no $s$-$t$ path in the residual network. You can check this in time $O(|E|)$.
Yuval Filmus's user avatar
4 votes

What actually is Blocking flow problem?

A blocking $s$-$t$ flow is a flow whose residual network (consisting of all edges not saturated by the flow) contains no $s$-$t$ path. Stated differently, a blocking flow is a flow which, for every $s$...
Yuval Filmus's user avatar
4 votes
Accepted

Can max-flow with mutually exclusive edges be reduced to standard max-flow problem?

You can reduce SAT to this version. Connect the source to nodes $x_1,\ldots,x_n$, one per variable, with infinite capacity. Connect each $x_i$ to two exclusive nodes $x_i^T,x_i^F$, with infinite ...
Yuval Filmus's user avatar
4 votes

Effect of increasing the capacity of an edge in a flow network with known max flow

I am assuming that you are given the flow on each edge which corresponds to the maximum flow for the graph $G$. So $f_e$ is the flow on edge $e$. I am also assuming that all the capacities and flows ...
foo's user avatar
  • 41
4 votes

Max flow with priorities

First, build an algorithm to solve the following problem: Given a threshold $t$ and a flow graph $G$, find the solution that maximizes $N_2$, subject to the requirement that $N_1 \ge t$. That ...
D.W.'s user avatar
  • 162k
4 votes
Accepted

Flows with Negative Values?

The maximum flow calculated using only positive flow values on each edge can indeed be smaller than the maximum if flow can also be negative. You can easily see why in a trivial graph with only two ...
Blckknght's user avatar
  • 386
4 votes

Multi-type max-flow

This is an instance of multi-commodity network flow. If you insist on integer flows, the problem is NP-hard, but if you allow flows to take fractional values, the problem can be solved in polynomial ...
D.W.'s user avatar
  • 162k
4 votes

Does minimum cost flow problem work for real valued edge weights/costs?

In the case of the Ford-Fulkerson algorithm, yes, it's due to complexity. When the edge weights/capacities aren't integers, things get really annoying, really fast. If you allow all real numbers, ...
user116037's user avatar
4 votes
Accepted

Why CLRS example on residual networks does not follows its formula?

That's not what the formula gives you. As the caption says, the capacity of the augmenting path in the residual network in (b) is $4$. Therefore we send 4 units of flow along the augmenting path ...
D.W.'s user avatar
  • 162k

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