# 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
Filter by
Sorted by
Tagged with
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
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
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
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
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$ (...
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". ...
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 ...
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
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
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
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
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
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
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
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
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 ...
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-...
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
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
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 ...
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?
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
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
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
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
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
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
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
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
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
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
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
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 ...
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 ...
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 ...
1 vote
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
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
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
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 ...
1 vote
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
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 ...
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
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,...
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
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
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
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
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