27

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


14

The complement of a maximum independent set is a minimum vertex cover. To find a minimum vertex cover in a bipartite graph, see König's theorem.


9

Note: The notations and definitions used below are borrowed from the third edition of the book. To answer this question, first, observe that if $(u,v) \notin E$, then by flow definition, $$f(u,v) = f'(u,v) = (f \uparrow f')(u,v) = 0 \, .$$ Furthermore, since $f'(v,u) \le c_f(u,v) = f(u,v)$, it is obtained that $f'(v,u) = 0$. This simply implies that $\...


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

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


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

There is a paper titled "Dynamic Trees in Practice" which reviews the practical implementation. The other categories that Link-Cut tree could be used efficiently is in Database Indexing. You can find this in the book "Database Index Techniques".


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

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


5

In general, the answer is no. If we put XOR-like restrictions on the out-going edges of a vertex, we can prove that finding a min-cut-max-flow is NP-Hard. The technique is to reduce 3-SAT to it. Let's assume there are $n$ variables $x_1, x_2, ..., x_n$ in the 3-SAT and $m$ clauses $c_1, c_2, ..., c_m$. We create a graph $G(V,E)$ encoding the instance of the ...


5

A very simple approach for question 2 is the following. Sort the edges by capacity. Remove the edge with lowest capacity, and check if there is still a path from $s$ to $t$. If there is, move on the edge with the second lowest capacity, and so on. At some point, we will disconnect $s$ from $t$ by removing an edge of capacity $c$. Now, we know that $c$ is ...


5

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


5

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


5

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.


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


4

The solution given is clearly incorrect, as you demonstrate with the counterexample. Note that the graph U+V is a connected component by the infinite-capacity edges. Therefore every valid cut will have to contain all of A, B, C, D, E, F on the same side. Trying to trace back where the solution came from: http://www.cs.washington.edu/education/courses/cse521/...


4

this paper finds at the end that a link-cut (LC) tree outperforms rake-compress (RC) trees for the Sleator/Tarjan max-flow algorithm using a standard Dimacs random graph generator. the paper focuses on change propagation as one application of dynamic trees. eg, change propagation is similar to the way that excel spreadsheet cells have to be recomputed on ...


4

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


4

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


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

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


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

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


4

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


4

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


4

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 time using linear programming.


4

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 from $s$ to $t$, namely, the path $s \to v_2 \to v_3 \to t$. In particular, $f(s,v_2)=8$, $f'(s,v_2)=4$, and $f'(v_2,s)=0$, so the updated flow is $8+4-0=12$.


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