Questions tagged [network-flow]
Network flows are used to model concepts like traffic or water pipe systems. The basic idea is to move as many units of flow from source to sink nodes via edges with limited capacity.
361
questions
3
votes
5
answers
2k
views
Why is this flow a max flow?
According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how ...
- 31
6
votes
2
answers
3k
views
Does Ford-Fulkerson always produce the left-most min-cut
When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found.
However, if you then use the left-over residual graph to produce a min-cut ...
- 416
4
votes
1
answer
1k
views
Ford-Fulkerson Running Time
This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them!
In the analysis of Ford-...
- 71
3
votes
1
answer
920
views
Maximum Flow with Binary Capacities
Consider the problem of finding a maximum flow from node $s$ to node $t$ in a directed graph where each link has capacity either $0$ or $1$. What is the state of the art regarding how fast this flow ...
- 75
-1
votes
1
answer
616
views
Intuition behind the max-flow min-cut theorem
What is the intuition behind the max-flow min-cut theorem?
I know that the min-cut is the dual of max-flow when formulated as a linear program, but the result seems artificial to me.
- 36
1
vote
0
answers
54
views
Network clearance algorithms
In the network clearance problem,
we are given a simple undirected graph with a capacity assigned to each edge (and/or to each vertex).
Each edge can transport up to its capacity each time step (i.e., ...
- 541
2
votes
2
answers
223
views
Literature on network-flow (optimization) approximation algorithms
I've been searching on literature on approximation algorithms in the context of network-flow problems (optimization) to finish my bachelor degree.
However, I have been looking in several well-known ...
- 501
3
votes
1
answer
900
views
Linear programming formulation of cheapest k-edge path between two nodes
Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges.
Here is my attempt using a flow network:
\begin{align}
\...
- 67
3
votes
1
answer
770
views
"Minimum" maximum flow with extra capacities
Problem:
Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, ...
0
votes
0
answers
41
views
Algorithm: "Minimum" maximum flow with extra capacities [duplicate]
Problem:
Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, ...
2
votes
0
answers
732
views
Does Edmonds Karp take back-edges into account?
I amb doubting with the implementation of the Edmonds-Karp implementation of the Ford-Fulkerson algorithm.
This is a problem with flow networks.
As I understand the algorithm, it consists on taking ...
- 327
3
votes
1
answer
1k
views
Global relabeling heuristic: Push-relabel maxflow
I have a correct, working implementation of the preflow-push-relabel maxflow algorithm [2]. I am trying to implement the global relabeling update heuristic [3], but have run into some issues.
I have ...
user26203
3
votes
1
answer
222
views
Unsplittable flow in capacitated networks
I have an undirected network with capacitated links/edges. Between some nodes unsplittable traffic has to be routed. All demands and capacities are known, but it is uncertain if all flows can be ...
- 131
1
vote
0
answers
32
views
MaxSNP flow problems
Currently, I'm trying to understand the definition and notion of MaxSNP and MaxSNP-hardness. I see that several combinatorical problems such as Max-3SAT are in MaxSNP since one can easily express them ...
- 622
2
votes
1
answer
1k
views
Getting ALL negative weight cycles of a graph using Bellman-Ford
I'm doing a min cost assignation problem to assign doctors to their working days for a hospital.
After correctly getting the max flow with Ford-Fulkerson algorithm, I would like to use the cycle ...
- 121
13
votes
4
answers
41k
views
How to find a minimum cut of a network flow?
I am currently reading the lecture slides from Princeton regarding network flows but I cannot understand how they manage to find out minimum cuts from a directed graph.
Could someone explain how to ...
- 141
19
votes
2
answers
2k
views
Compute a max-flow from a min-cut
We know that computing a maximum flow resp. a minimum cut of a network with capacities
is equivalent; cf. the max-flow min-cut theorem.
We have (more or less efficient) algorithms for computing ...
- 72k
1
vote
1
answer
1k
views
Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)
Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
- 501
2
votes
2
answers
139
views
Are there FPTASs for the min cost flow problem?
In literature, one can find many approximation algorithms for the multicommodity min cost flow problem or other variants of the standard single-commodity min cost flow problem. But are there FPTASs ...
- 622
1
vote
1
answer
1k
views
Ford-Fulkerson algorithm clarification
In the second edition of the book of Cormen "Introduction to Algorithms" appears the following example (in the left part is the residual network while in the right part shows the flow results):
I ...
- 163
2
votes
0
answers
54
views
Distributed push relabel with changing graph topology
There is at least one (1) distributed version propsosed for the push-relabel maximum-flow algorithm. I wonder if and how this algorithm can cope with nodes leaving or enterig the graph during runtime. ...
- 267
-1
votes
1
answer
109
views
Determine whether there is a valid rounding in a table of numbers
I was told this question would be better suited here:
Suppose you have a table such as:
$\begin{array}{ccc}
11.998 & 9.083 & 2.919 &|& 24\\
12.983 & 10.872 & 3.145 &|&...
0
votes
0
answers
329
views
sum of max flow in residual graph and value of flow
My teacher today explained us this . Consider a network and suppose that at any stage during the application of the Edmonds Karp algorithm to find the max flow, let
...
- 1
6
votes
2
answers
1k
views
Finding a subset in bipartite graph violating Hall's condition
We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are ...
- 187
3
votes
0
answers
223
views
Efficient update to rational flow network?
Once we've computed the max flow in a flow network with integral capacities, we can change one of its edges' capacity by a unit and recompute a maxflow in linear time using BFS. Is there something ...
- 2,019
2
votes
0
answers
120
views
Max Flow on low depth DAGs
I have a family of acyclic networks in which every path from the source of a given network to its target has length exactly $3$. I'm aware of a publication that in general, finding a max flow in a DAG ...
- 2,019
4
votes
1
answer
665
views
Complexity of the decision version of determining a min-cut
I was wondering what the complexity of the following problem is:
Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$.
Question: Is there an $s$-$t$ cut of capacity at most $k$?
...
- 171
1
vote
1
answer
1k
views
For a flow network, is it possible to show that there always exists a maximum flow which would assign integer values to all the edges? [closed]
Is it possible to prove that for a flow network, there always exists a maximum flow which assigns an integer value to every edge?
- 11
2
votes
3
answers
445
views
Can not follow the example for max-flow-min-cut on Wikipedia
This Wikipedia example is very confusing. Its saying the max flow = min cut. But I see the max flow = 9 and the min cut = 7. If not, how does the capacity =min cut here? Which is the max flow min cut ...
- 461
2
votes
2
answers
200
views
Don't understand this graph definition
I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows:
Given a graph $G= \langle V_G, E_G \...
- 339
2
votes
1
answer
1k
views
Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths
Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut (...
3
votes
2
answers
2k
views
What is the difference between maximal flow and maximum flow?
What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a ...
- 31
1
vote
1
answer
620
views
Minimum cut versus sparsest cut? [closed]
My question is that I'm trying to find the sparsest cut in a connected, undirected graph (all weights are = 1). Basically, I am looking trying to find the smallest cut (i.e., number of edges cut since ...
- 11
1
vote
1
answer
1k
views
maximum bipartite matching
I am working out with the rooks problem. If there are m rooks on an nxn chessboard,i have to give describe a polynomial (in m and n) time algorithm that finds a maximum-sized subset of the rooks such ...
- 69
0
votes
0
answers
77
views
Picking an optimal initial congestion window size (high bw, high latency and short bursts)?
What is a known strategy to approach a situation where short bursts of data are being sent very often over a high bandwidth, high latency cable? I am aware of cubic but even that does not utilize a ...
- 231
5
votes
3
answers
1k
views
Maximum number of matched vertexes in a one-to-many bipartite graph
I have a variant of bidding problem at hand.
There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who ...
- 53
0
votes
1
answer
218
views
Network Flow with multiple connected subsets
Given a set of buyers, houses, agents with the following constraints:
Agents only know a subset of buyers
Agents only know a subset of houses
Agents can only do some amount of transactions
...
- 109
8
votes
1
answer
158
views
Why can't you write the 2-paths problem as a max-flow problem?
This is a follow-up question to this. Consider the 2-paths problem:
Given a directed graph $D=(V,A)$ and pairs of vertices $(s_1,t_1)$ and $(s_2,t_2)$, are there paths $P_1 = (s_1,\dots, t_1)$ and $...
- 669
3
votes
0
answers
1k
views
Node potentials of minimum cost flow successive shortest path algorithm
I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
- 231
1
vote
1
answer
215
views
Prove that every maximal flow yields the same minimal cut
Hi I'm trying to prove the following proposition:
Given a network $G,s,t,\omega$ where $\omega$ is the capacity, create a minimal cut cut ${S=\left\{ (s,v)\in E_{G_{r\_max}}\right\} }$ where $G_{r\...
- 63
2
votes
0
answers
229
views
residual network for a network with lower and upper bounds?
How does one construct the residual network in such a case?
The formula is for edge $(u, v)$ is
$$rf(u,v) = (c_{\mathrm{upper}}(u,v) - f(u,v)) + (f(v,u) - c_{\mathrm{lower}}(v, u))\,,$$
where $rf(...
- 121
5
votes
0
answers
644
views
Understanding Dinic's algorithm using dynamic trees
I have here a directed graph that I used to perform Dinic's algorithm to find maximum flow. I need to adjust this graph and this algorithm to work with dynamic trees (i.e. the Sleator-Tarjan algorithm)...
1
vote
1
answer
772
views
Finding paths from the result of max flow [closed]
Suppose that I have run maxflow algorithm on a graph G and, as a result, I have a set of edges with flow on them.
I would like to enumerate all possible sets of paths that comprise the maxflow.
That ...
- 27
2
votes
2
answers
827
views
State machine with knowledge of prior states?
I'm attepting to model a process flow where the transition to the next state is occasionally based on not only the input to the current state, but a prior state as well.
Below is an example graph ...
user8632
2
votes
1
answer
104
views
Multicommodity circulation formulation
On the circulation problem page on wikipedia, the multicommodity circulation problem formulation seems to be insufficient, since we can just set all but one flow to $0$, and reduce it to a circulation ...
- 3,023
9
votes
1
answer
10k
views
Effect of increasing the capacity of an edge in a flow network with known max flow
I need your help with an exercise on Ford-Fulkerson.
Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance.
Now suppose you are given an ...
- 237
2
votes
3
answers
4k
views
In flow networks, may source/sink have incoming/outgoing edges?
I was wondering. May the source and sink have in-out going edges in a flow-network, and if so - does Ford-Fulkerson and the max-flow min-cut theorem apply ?
Flow-networks are always pictures with no ...
4
votes
2
answers
3k
views
Maximum number of augmenting paths in a network flow
Let's say we a have flow network with $m$ edges and integer capacities.
Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.
A good way to start thinking ...
- 323
20
votes
2
answers
2k
views
Are link-cut trees ever used in practice, for max flow computation or other applications?
Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as link-...
- 301
0
votes
1
answer
137
views
Push relabel algorithms in flow networks
In the CLRS book (http://en.wikipedia.org/wiki/Introduction_to_Algorithms) Chapter 26 (Maximum Flow) page 744 (third edition), there is the following equation -
$$
\sum_{u \in U}e(u) \;=\;
\sum_{u \...
- 103