36 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 ...
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')$ (...
user avatar
11 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)...
user avatar
  • 143k
9 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 ...
user avatar
  • 460
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 ...
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 ...
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 ...
user avatar
7 votes
Accepted

Finding a subset in bipartite graph violating Hall's condition

Let $G=(X,Y,E)$ be a bipartite graph with $|X|=|Y|=n$ having a maximum matching $M$. Consider the directed graph $G'$ on the vertex set $X \cup Y$ which includes the edges of $G$ oriented from $X$ to $...
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$...
user avatar
  • 86
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 ...
user avatar
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.
user avatar
6 votes

Remove minimum number of vertices to disconnect the graph

(This answer was originally given as part of the question, with the goal of it being verified.) My intuition tells me that we can use max-flow, min-cut algorithm to solve this problem: Replace each ...
6 votes

Why is this flow a max flow?

You've left out part of the statement. It should be "If there's no path between the source and the sink with unused capacity the flow is a max flow." If you look at your graph you'll see that there ...
user avatar
  • 7,853
6 votes
Accepted

Does Ford-Fulkerson always produce the left-most min-cut

Yes, Ford-Fulkerson always finds the cut that is "closest" to the source. See this question for a formalization of what is meant by "closest". A graph can contain exponentially many min-cuts, so ...
user avatar
  • 143k
6 votes
Accepted

Will the Ford-Fulkerson algorithm always find the max flow if we start from a valid flow?

Yes. If the flow is not maximum, then there is an augmenting path. If there's an augmenting path, Ford-Fulkerson will find it (and continue to find them until the flow is maximum). Starting from a ...
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 ...
user avatar
  • 497
6 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 ...
user avatar
5 votes

Ford-Fulkerson Running Time

There might be some more clever trick in the analysis to get rid of the $V$, but at the very least, I can provide some intuition as to why you can get rid of it. With Ford-Fulkerson, it is generally ...
user avatar
  • 29.2k
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 ...
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 ...
user avatar
  • 143k
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 ...
user avatar
5 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. ...
user avatar
  • 12.4k
4 votes

Literature on network-flow (optimization) approximation algorithms

In his FOCS2013 (Best Paper award) work, Aleksander Mądry gives a $\widetilde O(m^{\frac{10}{7}})$-time for exact max-flow and gives a nice survey on the existing techniques (including near-linear ...
user avatar
  • 2,594
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 ...
user avatar
  • 41
4 votes

Why not use the channel capacity as the sliding window size?

Sliding windows are used to: Keep track which packets were sent and received, hence the data transmission is reliable Keep track of the memory available to the receiver. The receiver may fill its ...
user avatar
  • 797
4 votes

Residual Graph in Maximum Flow

The intuition behind the residual network is that it allows us to "cancel" an already assigned flow i.e. if we have already assigned 2 units of flow from $A$ to $B$, then passing 1 unit of flow from $...
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 ...
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$...
user avatar
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 ...
user avatar
  • 396
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 ...
user avatar
  • 143k

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