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.
126
questions with no upvoted or accepted answers
20
votes
1
answer
2k
views
Could min cut be easier than network flow?
Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
D.W.♦
- 156k
13
votes
2
answers
1k
views
Flow graph that requires pushing back flow in Ford Fulkerson
Does there exist a flow graph that always requires flow to be pushed back no matter what ordering of augmenting paths is chosen in Ford Fulkerson?
Let's assume we use the standard procedure of ...
- 4,431
9
votes
1
answer
1k
views
Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?
We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
- 261
8
votes
1
answer
303
views
Complexity of removing edges to eliminate a perfect matching
Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this ...
- 81
6
votes
0
answers
1k
views
A variation in Ford-Fulkerson algorithm
Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow.
I was thinking that when we augment a path ...
- 377
5
votes
0
answers
73
views
Network Reconstruction from Flow Function
Suppose that $T$ is a set of vertices in an unknown network.
We have oracle $F(X,Y)$ that returns maximum flow value between $X, Y \subseteq T$ in the unknown network.
Can we reconstruct the unknown ...
- 51
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)...
4
votes
0
answers
174
views
Solving the maximum flow problem in the real world
Is it possible to solve the maximum flow problem in the real world, ie. using water running through physical pipes? So you would have a tap at the source node, pipes of various diameter (depending on ...
4
votes
0
answers
171
views
Successive Shortest Paths vs Ford–Fulkerson
Can someone explain how exactly Successive Shortest Paths (SSP) is a generalization of the Ford–Fulkerson algorithm? I've found this stated in a few papers and websites as well as the Wikipedia page ...
- 69
3
votes
0
answers
133
views
Deciding whether a given flow is unique in $O(\lvert V \rvert + \lvert E \rvert)$ time
I am stuck with the following exercise:
Is it possible to decide whether a given flow $f$ is a unique mamimum flow in $O(\lvert V \rvert + \lvert E \rvert)$ time?
I am not sure that this is possible....
- 457
3
votes
0
answers
236
views
How to achieve a "balanced" min-cost flow solution
I'm not too familiar with minimum cost flows, so please bear with me. I need to calculate the minimum cost flow for a network that looks like this:
(The numbers in parentheses next to nodes indicate ...
- 153
3
votes
1
answer
184
views
Max flow algorithm for floating-point weights and E~=10*V
Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e. ...
- 131
3
votes
0
answers
254
views
Introduction to the Traffic Light Scheduling Problem
I would like to understand the basics of how traffic light scheduling works. Looking through research papers the topics typically revolve around actual highway systems in urban areas, but also ...
- 2,163
3
votes
0
answers
74
views
Can we create the level graph from sink to source in Dinitz?
One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS.
Could we create the level graph from sink to source ...
- 141
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
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
2
votes
0
answers
17
views
Inverted Min Cost Max Flow
I'm starting to think there's no possible solution to this problem, but before jumping to conclusions I want to confirm it with collective knowledge.
Let's imagine that there's a 2D grid, where S ...
2
votes
0
answers
51
views
State of the art implementations of minimum-cost multicommodity flow approximation algorithms
I'm looking for implementations of approximation algorithms (or algorithms that would be meaningful to implement for use in practice) for the minimum-cost multicommodity flow problem as defined in e.g....
- 165
2
votes
0
answers
314
views
Finding the cut with the minimum number of edges (including reverse ones)
I do not know how to solve the following problem:
Given a directed graph $G$ with a two nodes $s,t \in V(G)$ find a cut $(S,T)$ with $s \in S$ and $t \in T$ such that $(S,T)$ has the minimum number of ...
- 457
2
votes
0
answers
121
views
Min Cost Max Flow algorithms for providing multiple solutions
Minimum Cost Maximum Flow algorithms have been known to provide an optimal flow routing for network flow problems in satisfactory runtime. Some of the algorithms for solving a min-cost max-flow ...
- 21
2
votes
0
answers
150
views
The max-min resource assignment problem
I am wondering if there are any results for the following max-min assignment problem:
Given $n$ machines $C = \{C_1, C_2, \dots, n\}$ with the $k$-th machine has power $C_k$. There are $m$ tasks $T = \...
- 21
2
votes
1
answer
168
views
Ensure a vertex has the highest flow in max-flow algorithm
Let's suppose we have a supplier, sorting facilities, shipping companies and
a target warehouse.
We produce n packages of the product, and each goes to a different sorting facility (so every facility ...
- 21
2
votes
0
answers
95
views
Find a maximum flow that also maximizes the flow over a specific edge
Let $G=(V,E,c,s,t)$ be a flow-network, where $s$ is the source, $t$ is the target, and $c:E\mapsto [0,\infty)$ defines the capacity of every edge in the network. Let $e=(u,v)$ be an edge in the ...
- 163
2
votes
0
answers
144
views
Add capacity to the uni-weighted graph to increase max flow
Given a uni-weighted graph G (in which each edge has the capacity of 1), and we have k extra capacities (k is an integer) that we can spend on any subset of existing edges. That is, we can increase ...
- 21
2
votes
0
answers
41
views
FPTAS algorithm to find flow at each link for multi commodity flow problem?
Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the ...
- 23
2
votes
0
answers
37
views
Transit scheduling using flow networks
I am studying the maximum/minimum flow question, and was given the following problem:
A traveling agency has $n$ destinations on their service map, and it intends to maintain them with minimum ...
2
votes
0
answers
117
views
Find optimal redistribution in flow graph
I have directed graph (maybe with cycles), and some resources in vertices (let's say gold). I can transfer gold between vertices only in direction of edges. The task is to minimize maximum value of ...
- 121
2
votes
0
answers
159
views
long-lived scheduling using max-flow & push/relabel
I'm writing a scheduler of long-lived Processors which execute long-lived Tasks. Processors and Tasks may each come and go over time, at any time (when a Processor departs, its assigned Tasks now ...
2
votes
0
answers
47
views
Card Shuffling, Bounding Mixing time using Paths and Flows
I've been struggling with a problem that is very similar to a 2014 question posted here. The question in particular is 3(1) and 3(2).
To paraphrase, we are supposed to use paths and an encoding ...
- 463
2
votes
0
answers
562
views
Bhandari Algorithm: Canceling Edges
I have a quick question on implementing the Bhandari algorithm. I do not have the textbook where the algorithm is originally given (Bhandari, Ramesh (1999). Survivable networks: algorithms for ...
- 121
2
votes
0
answers
1k
views
Minimum Cost Max Flow with Negative Weight Cycles?
Does there exist an algorithm that can solve the minimum cost maximum flow problem even if the residual graph contains negative weight cycles?
I have an implementation that uses shortest paths to ...
- 1,198
2
votes
0
answers
403
views
Minimal Separator / Vertex disjoint Paths
I'm in need of implementing the algorithm to actually locate the minimal vertex separators set of the whole graph (not just s-t).
It is my understanding that this can be done by doing the s-t ...
- 171
2
votes
0
answers
145
views
How to construct a network flow problem?
I have the optimization problem given below
max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$
s.t
$\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$
$\quad 2)\quad x_{ij} \in {0,1}$
$\quad ...
- 41
2
votes
0
answers
315
views
Complexity class of maximum flow problem with random arc capacity
Given a graph $G=(N,E)$ with a special source node $s$ and sink node $t$. There is a subset of arcs $E^* \subset E$ that has the capacity drawn from a probability distribution $F$ independently. Then ...
- 41
2
votes
0
answers
199
views
Cheeger constant of a graph versus conductance of a Markov chain
Given some graph $G$ with vertices $V$ and edges $E$, its Cheeger constant $h(G)$ is well defined as
$$ h(G) = \min_{S\subset V,0<|S|\leq|V|}\frac{|\partial S|}{|S|}. $$
Given some doubly-...
- 206
2
votes
0
answers
736
views
How can we add back edges in Ford - Fulkerson algorithm?
I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent ...
- 135
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
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
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
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
1
vote
1
answer
17
views
Max flow, min cost with upper and lower bounds
:)
I am trying to implement an algorithm that fairly distributes people into groups, given their ranking of those groups, while also taking into account their preference for partners.
I have modeled ...
- 11
1
vote
0
answers
28
views
Lower bounds on max-flow and assignment problems
As far as I know, all existing strongly polynomial algorithms for flows and assignment problem have $\Omega(V^3)$ complexity in the arithmetic model (assuming the graph is dense). I'm interested in ...
- 11
1
vote
0
answers
16
views
epsilon-optimality in cycle-cancelling for min cost flow
I'm learning about the (min-mean) cycle-cancelling alg for min-cost flow in Ahuja, Magnanti, and Orlan's Network Flows book (Chapters 9 and 10). When talking about the alg, they prove this fact ...
- 21
1
vote
0
answers
78
views
Why in Edmonds Karp or Ford Fulkerson Algorithm the time complexity of BFS or DFS respectively is O(E) rather than O(V+E)?
For these algorithms, the time complexity of BFS and DFS is O(E).
I have gone through many websites and even the algorithm books, but I never got a clear idea of why it is O(E). It just says it's O(E) ...
- 11
1
vote
0
answers
40
views
Networks and data flow - graph algorithms for propagating updates from nodes correctly
Suppose I have an acyclic directed graph of Nodes which subscribe to Events. When an Event callback is activated for some Node, the Node's internal update() method is called. Then, because the Node ...
- 837
1
vote
1
answer
15
views
Defining multi commodity flows as polytopes
In a multi commodity network, we define a demand to be a vector $d \in \mathbb{R}^{k}$, where $k$ is the number of pairs of sinks. That is, $k = \binom{S}{2}$, where $S$ is the set of sinks (aka ...
- 334
1
vote
0
answers
88
views
Successive shortest paths with fixed costs and costs per unit
I have a directed graph $G(V,A)$ with arc costs $c_{ij} = \alpha_{ij}1_{x_{ij}>0} +\beta_{ij}x_{ij}$, where $\alpha_{ij}$ and $\beta_{ij}$ are, respectively, a fixed cost and a cost per unit of ...
- 111
1
vote
0
answers
63
views
Max flow in bipartite network where all vertices on the left hand side have degree exactly $2$
I have a flow question which I'm stumped on but seems like there should be an answer that I am not seeing.
Consider a network with a start $s$ and an end $t$ and a bipartite graph $L \cup R$. $s$ is ...
- 123
1
vote
0
answers
138
views
Finding maximum weight closure of a graph using min-cut
I am going through the book "Network Flows" by Ahuja et al. In chapter 19.2 "MAXIMUM WEIGHT CLOSURE OF A GRAPH", I find this example of turning a vertex-weighted (positive or ...
- 111