# Tag Info

### 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 ...
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')$ (...
Accepted

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

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

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

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

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

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

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

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

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

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