# Tag Info

35

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 problem for the following network $G$ (where each label $f_e/c_e$ denotes both the flow $f_e$ pushed through an edge $e$ and the capacity $c_e$ of this edge): One ...

11

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)+k$ in the transformed graph, where $k$ counts the number of edges crossing that cut. Note that if you consider any cut in the original graph with larger ...

10

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')$ (this edge is saturated) and we decrease the capacity in $1$ unit. You need to remove one unit of flow from $s$ to $t$ that goes through edge $e'$. Let say that ...

9

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 the source to all reachable nodes, these nodes define one part of the partition. Call this partition $A$. The rest of the nodes (the unreachable ones) can be ...

8

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 new vertex $s'$ and an edge $(s',s)$ with weight $w$, a minimum $s',t$-cut in the new graph consists of just the edge $(s', s)$ but that doesn't give any ...

8

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 edge which you can use to throttle the flow. The edge from A to B is the only edge out of A and the only edge into B.

7

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 $Y$ and the edges of $M$ oriented from $Y$ to $X$. Let $U \subseteq X$ be the set of vertices of $X$ unmatched in $M$, and let $S$ be the set of vertices ...

7

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$-matching in bipartite graphs. In case you are unfamiliar with the maximum $b$-matching problem, this is a generalization of the matching, defined as follows:...

7

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 solving these problems is linear programming and you could easily modify the normal multicommodity flow program to deal with your situation, just by substituting zero ...

7

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 way does add information, since $f_{max}$ can be much smaller than $|V||E|$ -- and this is the only time when you might otherwise consider using some other ...

7

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.

6

The proposed construction does find two vertex disjoint paths from s to t (if they exist). HOWEVER, the paths might be $P_1=(s_1,…,t_2)$ and $P_2=(s_2,…,t_1)$, which is not what we want.

6

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 beware that any procedure to enumerate all min-cuts must take exponential time in total in the worst case. Based on what I've read, there are output-sensitive ...

6

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 is no path with unused capacity all the way from $s$ to $t$. The $s$ to $a$ link has spare capacity but $a$'s lone outbond link is saturated. The $s$ to $c$ ...

6

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 different initial flow does not change this.

6

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 literature and can be solved in polynomial time with a reduction to the Assignment Problem. With the introduction of colors to the problem, it is NP-hard (and ...

6

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 the capacity of $\small e$ by $\small 1$, the maximum flow increments by at most $\small 1$. Hence, starting with the current max flow $\small f$, you only need ...

5

As saadtaame mentions, maximum usually means global maximum, whereas maximal means local maximum. For example, a maximal independent set in a graph is one to which no vertex can be added (making it a dominating set), while a maximum independent set is one with largest cardinality among all independent set. My guess is that a maximal flow is one in which ...

5

(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 of the undirected edges with a pair of directed edges. Replace each vertex $v$ with two vertices $v_\text{in}$ and $v_\text{out}$ connected by an edge. all the ...

5

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 assumed that you are working with connected graphs. For any connected graph with $V$ nodes, there are at least $V-1$ edges, since each node needs at least one ...

5

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 BFS (the residual graph is just the original graph where we removed full edges). Now, the idea of the proof in Introduction to Algorithms is to introduce a ...

5

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 carving, image denoising, stereo image correspondence, and more. See, e.g., https://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision, What's the ...

5

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 close a cycle. If you're not back where you started, you continue following an arbitrary path until closing a cycle, and so on. If you are back where you started, ...

5

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. Any edge $u \to v$ in $G$ with we can replace with two nodes $s, t$ and two edges $s \to v$ and $u \to t$ where one of the edges has the original cost, ...

4

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 values are integral. Now given this information, capacity of an edge $e$ is increased by 1. Therefore, the mincut value can increase by at most 1 implying ...

4

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 time for $(1+\epsilon)$-approximation in undirected graphs).

4

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 buffers and tell to the sender to slow down (because more packets will simply be dropped, causing the sender to re-send them with a probably bigger delay) When ...

4

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 $B$ to $A$ is interpreted as cancelling one unit of the original flow from $A$ to $B$.

4

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 capacity. Create one node per clause, and connect a literal to a clause (with infinite capacity) if the clause contains the literal. Finally, connect each clause to ...

4

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$-$t$ path, saturates at least one edge. Equivalently, a blocking flow is a flow which, for every simple $s$-$t$ path, saturates at least one edge. The ...

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