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
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
1
vote
1
answer
1k
views
Minimal set of rows and columns covering all non-zero entries in matrix
Given a matrix $A \in \{0,1\}^{n \times n}$, use network flows to describe an algorithm that finds the minimal set $I$ of rows and columns such that any non-zero entry is in one of the rows or columns ...
- 19
0
votes
0
answers
166
views
Will the Ford-Fulkerson method return any value if the residual network is ignored?
The normal Ford-Fulkerson method finds augmenting paths (as long as one exists) while including "back-flows", but if those back-flows are ignored, does there exist a flow network for which algorithm ...
- 141
0
votes
0
answers
538
views
Running Time of Ford Fulkerson where all edges have equal capacity
My intuition says it would simply be the number of edges leaving s.
I'm assuming it's a valid flow network so sum of capacities leaving s is the same as the sum of capacities entering t, so a max flow ...
- 101
1
vote
1
answer
4k
views
Flows with Negative Values?
Define a "non-standard" flow to be a flow where the quantity flowing through an edge may be negative.
Formally, given a directed graph $G$, and two designated and distinct
vertices $s$ and $t$ (...
2
votes
1
answer
391
views
Question on pseudocode for Ford-Fulkerson in Kleinberg-Tardos Text
I am looking at the following pseudocode from the Kleinberg-Tardos text "Algorithm Design".
...
- 323
5
votes
3
answers
1k
views
Max flow with priorities
I'm studying a simple max flow problem:
Each type of object $a_1, a_2...$ can be stored in some of several stores $b_1,b_2...$. This is described by this graph:
There are $|a_i|$ objects of the type ...
- 221
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
1
answer
4k
views
What is the time complexity of finding the residual network in this case?
Here are the details:
(1) We are given a number $f$ of units of flow that we wish to transmit from the source node to the sink node. For example, $f=5$ units of flow (data or goods) should be ...
- 23
2
votes
1
answer
1k
views
Min-cut in DAGs with unit edge weights
I'm trying to better understand the min-cut problem for directed acyclic graphs. I understand that the minimum capacity cut has equal capacity to the max flow of a graph by the max flow-min cut ...
- 25
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
4
votes
1
answer
3k
views
Residual graph of a graph with bidirectional edges?
Let's suppose we have a directed graph $G$ which has at least a pair of vertices $v,w$ such that $(v,w) \in E, (w,v) \in E$.
$e.g:$
In the example, there is an edge going from $C$ to $A$ and ...
- 195
1
vote
1
answer
173
views
Optimal covering of 2D matrix elements given spatial constraints
I have a particular problem I need to solve, but I'm not sure how to classify the problem or pick the right algorithm to solve it. I'm hoping someone here can lead me in the right direction.
I've ...
- 113
0
votes
1
answer
132
views
How to balance the inflow and outflow of each vertex in a bipartite graph?
I have a situation where in a group of people, every person is trading with multiple people and giving them some money. It can be visualised as a directed bipartite graph with ...
- 101
2
votes
1
answer
185
views
Variant of bipartite matching, with real capacities from source and to sink, all others unlimited
I've got a variant of bipartite graph matching and I can't find any literature about it.
We have bipartite graph with real capacity edges from source to left vertices (the sum of which is 1), real ...
- 23
1
vote
0
answers
1k
views
Simple Path between 2 nodes passing through specific nodes
I have an unweighted undirected graph and I have to find if there exists a path between two vertices $u,v$ that visits set of specific nodes $A$. $A$ can contain $1-10$ nodes. No node can be visited ...
- 23
0
votes
0
answers
162
views
Edmonds-Karp Maximum Flow Algorithm
Referring to Tim Roughgarden's Lecture Note - 2 (page 11) on CS261 at Stanford following statement and the para seem quite confusing.
Claim: d(f) never decreases during the execution of the Edmonds-...
0
votes
0
answers
98
views
Push–Relabel Maximum Flow Algorithm $x_f(s)\leq0$
I'm looking at Push–Relabel Maximum Flow Algorithm (or Goldberg-Tarjan Algorithm) and trying to solve some homework question.
As part of the answer I'm trying to prove $x_{f}(s)\leq0$
during the ...
- 167
0
votes
1
answer
532
views
Maximum flow properties
I was trying to solve problems in max flow algorithms.
And I came across this MIT Lecture Quiz.
http://people.csail.mit.edu/moitra/docs/6854hw4.pdf
solution : http://people.csail.mit.edu/moitra/docs/...
- 31
0
votes
0
answers
81
views
Applying Ford-Fulkerson to settle a business lunch
I want to organize a business lunch with two societies $E_1$ (mine) and $E_2$. Each society is made of four people from the Executive management and 6 of the Financial Management. I want to organize ...
-2
votes
1
answer
32
views
What's the complexity of running an algorithm that searches over all cuts on a network and returns the minimum?
It's a question of a problem set. If I search for all possible cuts on a network graph and return the minimum, (so it will be equal to max flow), what will be the complexity of running this?
- 1
4
votes
1
answer
337
views
New Applications of Network Flow
I am thinking of explaining the topic of Network flow to an audience of computer sciecne students, and I want to make it more enjoyable by giving some real life examples where a software Developer may ...
- 41
2
votes
1
answer
1k
views
Maximum flow with edge demands: can't understand the example of transition to transformed graph in the lecture notes
TL;DR:
There're lecture notes about a very simple reduction from "maximum flow with edge demands problem to the maximum flow problem. But I can't get the new capacities at the picture:
E.g., look at ...
- 21
3
votes
2
answers
848
views
In a flow network, is it possible to restrict the flow going into a node?
For example, if a node has 2 edges going into it and two edges coming out of it all with capacity 1, is there a way to make it so that only 1 unit of flow can go through this node (without just ...
- 31
0
votes
0
answers
1k
views
Is there a procedural way to find minimum s-t cut without guessing cuts?
I was reading about max flow theorem and there I saw scenario where the min s-t cut is found. But wherever I searched they did it after knowing the max flow or by guessing the cuts by iterating ...
- 31
1
vote
0
answers
64
views
An impartial game of snake
There is a display of NxN (N<=90) pixels with some blocked pixels and a snake of width = 1 pixel and variable length and two players A and B play a game.
The game proceeds as follows -
Both ...
- 151
2
votes
1
answer
113
views
Improvement of algorithm due to constrained graph
This algorithm runs natively in O(V * E^2).
The description states that
The running time of O(V * E^2) is found by showing that each augmenting path can be found in O(E) time, that every time at ...
- 175
0
votes
0
answers
236
views
How to uniquely determine a min-cut? [duplicate]
There are possibly several min-cuts for the source and target nodes of a graph.
I think I can determine the same min-cut for the same graph by putting the following restriction
"if there are ...
- 984
1
vote
0
answers
211
views
Paris-Traceroute and Traceroute Difference
I am trying to understand the difference between Paris-traceroute and normal traceroute.
I am using this website ( https://paris-traceroute.net/about) and trying to get the idea, what is Paris-...
- 127
3
votes
1
answer
6k
views
Checking if a given flow is a maximum flow
I'm curious as to if there's any way to check (without having to run a 'whole' maximum-flow-algorithm) whether a given flow $f_e$ is the maximum flow of the flow graph $G$ in $O(|E|)$ time complexity.
...
- 265
1
vote
0
answers
135
views
End-to-end bandwidth allocation to n pairs of nodes
Suppose there is a weighted graph representing a network with available bandwidth. I want to allocate end-to-end bandwidth between a set of pairs of nodes to transfer data. I want to find a path and ...
- 11
2
votes
1
answer
230
views
Max flow not min cut?
I understand the relation between max flow and min cut, however I made this (simplified) graph, and I cant figure out why max flow seems to be different from my min cut. Im probably overlooking ...
- 23
0
votes
1
answer
1k
views
Sliding Window Protocol, waiting Time calculation
With regard to this explanation in finding Round Trip Time I tried attempting the following question
Question
Frames of $1000$ bits are sent over a $10^6$bps duplex link between two hosts. The ...
- 348
0
votes
0
answers
15
views
Relationship between flow and resource consumption in VNFs (Middleboxes)
A middlebox consumes some resources (CPU ticks, RAM, etc.) to process a traffic, e.g., a IDS consume 50% CPU and 20% RAM to process a 100M bps flow.
Here is the problem. 100M bps flow may consume ...
2
votes
1
answer
264
views
Do not understand a lemma regarding dinics algorithm
Here you can find the following lemma with its proof.
Lemma: In a network with unit edge capacities,
Dinitz algorithm terminates after $O(\sqrt{m})$
blocking flow computations.
Proof:
Consider the ...
user11941
1
vote
1
answer
251
views
Is there an example of Dinitz's algorithm running with the worst time complexity?
I am trying to find a network, where Dinic's algorithm makes $|V|^2*|E|$ steps. Clearly it cannot be a network with $3$ or less vertices, but I am not able to come up with a working example for quite ...
- 151
1
vote
1
answer
300
views
Operation of the Ford–Fulkerson algorithm given an almost maximum flow [closed]
I have been assigned the question:
Let $G$ be a flow network and $f^*$ be the maximum flow computed by the Ford-Fulkerson algorithm. Consider a new flow network $G'$ constructed by increasing the ...
- 121
4
votes
1
answer
157
views
Allocating flows in a network while avoiding a particular node
I am considering a network with the max flow problem in a particular situation. I have a set of flows which should pass a certain node A and and another set of flows which should avoid A and pass ...
- 229
-1
votes
1
answer
2k
views
Network Flow - Bipartite Matching: Doctors Without Weekends Problem
Problem
You've periodically helped the medical consulting firm Doctors Without Weekends on various hospital scheduling issues, and they've just come to you with a new problem. For each of the next n ...
- 101
1
vote
0
answers
204
views
What is the worst case scenario for Dinitz's algorithm?
The complexity of Dinitz's algorithm (used to find maximum flow in a network) is O(V²E). I am trying to find a network, which is forcing the algorithm to use as much steps as possible.
I was thinking ...
- 151
4
votes
1
answer
5k
views
Algorithm for solving incremental max flow problem
I am working on a project where I need to be able to compute the maximum flow between two nodes in a graph after one of the edge weights has been incremented or decremented by 1. The graph is directed ...
- 65
5
votes
1
answer
708
views
Min-cut in graph with demands/lower bounds
This week I read something about network flow from Algorithm Design. But I am confused about some concepts.
We say, if a graph G contains some nodes with demands, positive or negative, how to define ...
- 51
2
votes
1
answer
3k
views
Unique min-cut means unique max flow?
This is not a home work question.
Is that correct to say in a flow network, if min cut is unique then max flow must also be unique?
Assume we have two max flow in a network. Then for each max flow,...
- 97
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
9
votes
2
answers
3k
views
Reducing max flow to bipartite matching?
There's a famous and elegant reduction from the maximum bipartite matching problem to the max-flow problem: we create a network with a source node $s$, a terminal node $t$, and one node for each item ...
- 9,037
2
votes
1
answer
3k
views
What actually is Blocking flow problem?
I am facing a hard time understanding Blocking Flow problem. This is what I have understood till now : We have a graph and in blocking flow problem we find all shortest paths from source to ...
- 163
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
1
vote
1
answer
472
views
Can max-flow with mutually exclusive edges be reduced to standard max-flow problem?
I'm working with a flow network like the following:
The source s has four edges, each with capacity 1, out to the nodes A, B, C, and D. All of A, B, C, and D have edges to two other nodes, X and Y, ...
- 113