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.

109 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19 votes
1 answer
1k 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 ...
user avatar
  • 143k
13 votes
2 answers
831 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 ...
user avatar
  • 4,371
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 ...
user avatar
  • 261
8 votes
0 answers
248 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 51
5 votes
0 answers
602 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)...
user avatar
4 votes
0 answers
46 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 ...
user avatar
4 votes
0 answers
69 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 ...
user avatar
  • 151
4 votes
0 answers
155 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 ...
user avatar
  • 69
3 votes
0 answers
83 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....
user avatar
  • 423
3 votes
0 answers
78 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 ...
user avatar
  • 153
3 votes
0 answers
235 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 ...
user avatar
  • 1,911
3 votes
0 answers
209 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 ...
user avatar
  • 1,999
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 ...
user avatar
  • 231
2 votes
0 answers
82 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 ...
user avatar
  • 423
2 votes
0 answers
58 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 ...
user avatar
2 votes
0 answers
147 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 = \...
user avatar
  • 21
2 votes
1 answer
90 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 ...
user avatar
  • 21
2 votes
0 answers
43 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 ...
user avatar
  • 163
2 votes
0 answers
125 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 ...
user avatar
2 votes
0 answers
33 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 ...
user avatar
2 votes
1 answer
107 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. ...
user avatar
2 votes
0 answers
32 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 ...
user avatar
2 votes
0 answers
82 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 ...
user avatar
  • 121
2 votes
0 answers
148 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 ...
user avatar
2 votes
0 answers
41 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 ...
user avatar
2 votes
0 answers
535 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 ...
user avatar
  • 121
2 votes
0 answers
362 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 ...
user avatar
2 votes
0 answers
140 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 ...
user avatar
  • 41
2 votes
0 answers
282 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 ...
user avatar
2 votes
0 answers
189 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-...
user avatar
  • 206
2 votes
0 answers
676 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 ...
user avatar
  • 135
2 votes
0 answers
625 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 ...
user avatar
  • 327
2 votes
0 answers
52 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. ...
user avatar
  • 257
2 votes
0 answers
118 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 ...
user avatar
  • 1,999
2 votes
0 answers
215 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(...
user avatar
  • 121
1 vote
0 answers
22 views

Dominators when node not reachable

For the definition of domination [Wikipedia], a node $d$ of a control-flow graph dominates a node $n$ if every path from the entry node to $n$ must go through $d$. If node $n$ is not reachable from ...
user avatar
1 vote
0 answers
11 views

What are the locally optimal points in an LP formulation of the max flow problem?

I'm taking a grad level algorithms course and we just ended the course talking about linear programming, and we had previously talked about the max flow/min cut problem. Our professor said that the ...
user avatar
  • 111
1 vote
0 answers
99 views

Proof that if the residual network of a max flow has cycles then the max flow is not unique

Let $G = (V,E)$ be a directed graph with source $s$ and sink $t$ and $s \neq t$. For each edge $e \in E$, we have $c(e) \in \Bbb N$. also, we are given a max flow function $f$ on that network. Let $...
user avatar
1 vote
1 answer
125 views

find edges such that if decreased by one unit, the max flow decreases as well

We are given a flow network $G = (V,E,c)$, where $c$ is the capacity function as well as a maximum flow $f_m: E\rightarrow \mathbb R$ from $s$ to $t$. The goal is to find edges such that if decreased ...
user avatar
1 vote
0 answers
65 views

Maximum money that can be made

Came across the following question. All the answers provided there have used brute force, more or less. My hunch was that it could be solved using dynamic programming or perhaps, network flow ...
user avatar
1 vote
0 answers
32 views

Linear programming and network flow

I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, ...
user avatar
1 vote
1 answer
64 views

Maximum flow in integer flow network

Let's say you have a maximum integer flow function in a network with 7 directed edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of ...
user avatar
1 vote
0 answers
56 views

Partially defined boolean function

Consider a Boolean function $f(x_{1}, x_{2}, \dots, x_{n})$. The value of $f$ is defined on some set of inputs, and some inputs are undefined (let us label undefined value with $?$). It is possible to ...
user avatar
1 vote
1 answer
74 views

Covering maximal number of sets using fixed number of elements

I've encountered some problem which seems general enough to have already been solved. There is a set of objects $O=\{o_1, o_2,\dots,o_k\}$ and a family of sets $A_1,A_2,\dots,A_t \subseteq O$. For ...
user avatar
1 vote
0 answers
26 views

Maximum edge-disjoint flow

Consider the case where you have two types of flow, let's say "red" flow and "blue" flow. You want to send $k_r$ red flow and $k_b$ blue flow through a DAG $G$ from a source $s$ to a sink $t$ in such ...
user avatar
1 vote
0 answers
36 views

Getting rid of negative-cost edges in min-cost max-flow algorithmically

I have a min-cost max-flow problem. The designed network (without cycles) gives correct results using cycle cancelling, but it is way too slow. I would like to get rid of negative edges so that I can ...
user avatar
  • 163
1 vote
0 answers
201 views

Practice question on the applications of flows and cuts

This question is from Erickson's textbook on algorithms, p. 376, question 18. Faced with the threat of brutally severe budget cuts, Potemkin University has decided to hire actors to sit in ...
user avatar
  • 111
1 vote
0 answers
62 views

Binary flow in max flow problem

is there a way ensure that there only is flow through vertices c and d and not e or through d and e and not c. But not both at the same time. With an simple extension it is possible to put also ...
user avatar