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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
22 views

shortest path increases monotonically => a bound on the length of one iteration of Edmons-Karp is then O(E) ... Convince me this is true

I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/). Everything in the first part of the proof (The section ...
user avatar
1 vote
1 answer
28 views

Max flow bottleneck approach flow after k iterations

This is a question from a previous exam in Graph theory and algorithms, the correct answer is E but I don't understand why. Given a network flow $(G,c)$ over graph $G(V,E) $. Assume we run Edmonds-...
user avatar
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
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
1 vote
1 answer
45 views

Finding source-like nodes in a flow notework

Let $G$ be a flow network, where $c(e)$ is the capacity of an edge, and the source is $s$ and sink $t$. Define a node $v$ to be "source-like" if for every min-cut $(S,T)$ of $G$ where $S$ ...
user avatar
  • 293
0 votes
0 answers
25 views

Looking for an algorithm for multi-path funnel analysis

Suppose we have a dataset with each instance: {uid, action, TS}. The funnel algorithm (e.x https://clickhouse.com/docs/en/sql-reference/aggregate-functions/parametric-functions/#windowfunnel) looks at ...
user avatar
0 votes
1 answer
72 views

Show a reduction of max flow to min cost

Show a reduction of max flow to min cost (not min cost max flow!!)
user avatar
0 votes
0 answers
28 views

Lucky Ford Fulkerson

I know that Ford Fulkerson might not terminate. But if we assume we know in advance it terminates for some G, and we always pick the "correct" augmenting path, can we upper bound the number ...
user avatar
  • 149
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
0 votes
0 answers
55 views

Given a max flow, generate the residual graph

How do you generate a residual graph given the max flow path of a graph? I saw in this this Stack Overflow post. That in order to calculate the min-cut you can run Edmonds-Karp then get the residual ...
user avatar
  • 141
1 vote
1 answer
27 views

Proof that using residual network from Ford-Fulkerson will get you min-cut

So I'm following this article and they use the following algorithm to find the min-cut. Algorithm: Run Ford-Fulkerson algorithm and consider the final residual graph. Find the set of vertices that ...
user avatar
  • 141
0 votes
0 answers
17 views

Convert Linear Program to Network Flow

Given the following network flow problem: $$max \sum_{p \in P}x_p$$ $$s.t. \sum_{x_p \in c_e} x_p \leq c_e, \forall e\in E$$ $$x_p \geq0$$ $P$: All paths from a start node $s$ to end node $t$ $E$: Set ...
user avatar
  • 141
1 vote
1 answer
119 views

All nodes reachable from source in residual network of any max flow are included in $S$ for any min-cut $(S,T)$

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
  • 11
1 vote
1 answer
29 views

Using Flow graph to find maximum matching

I recently submitted an answer to the following question (homework in algorithms course): A guy has m shirts, n pants, and p belts. he wants to make the maximum amount of outfits while abiding by ...
user avatar
  • 13
0 votes
0 answers
12 views

How does Ford-Fulkerson checks that the flow respects the conversation of flow per node?

This is the pseudocode from Wikipaideia's article My question is: How does this algorithm checks for the conversation of flow during its running time ? I get that we never violate the constraint $f(...
user avatar
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
50 views

Finding 2 paths between 2 source-target pairs

Given an undirected graph $G=(V,E)$ and 2 sources $s_1,s_2$ and 2 targets $t_1,t_2$, I am looking to find paths $P_1$ and $P_2$, where $P_i$ is a path from $s_i$ to $t_i$ and $P_1$ and $P_2$ are edge-...
user avatar
1 vote
1 answer
44 views

Question about max flow: If all edges have capacity in integers, does a max flow exist where the flow in every edge is in integers?

Let's assume that for every $e\in E$ it holds that $c(e)$ is an integer. Does it mean that there exists a max flow $f$ that for every $e\in E$ it holds that $f(e)$ is an integer? It sounds obvious but ...
user avatar
2 votes
1 answer
51 views

Flow with edge-weight restrictions

I am given a graph $G=(V,E)$ undirected and two vertices, the source vertex $s$ and the target vertex $t$. Additionally, each edge comes with a capacity $c(e)$ (non-negative) and a set of weight ...
user avatar
1 vote
1 answer
43 views

How to reduce seating families at tables to maximum flow?

Problem: We have $p$ different families with $1 \leq i \leq p$ members for the $i$-th family. We also have $q$ tables where table $t_j$ has a capacity of $1 \leq j \leq q$. We want no two members of a ...
user avatar
2 votes
1 answer
68 views

Minimum number of edges to remove from a graph, so that MST contains a certain edge

Let's suppose we have a weighted and connected graph. We can easily find the minimum spanning tree for this graph. But let's say we want to "force" a certain edge $e$ to be in the MST. For ...
user avatar
2 votes
1 answer
72 views

Max-flow from a to c is at least the minimum of max-flow from a to b and max-flow from b to c

Given a directed weighted graph $G = (V, E, w)$, we refer to the max flow when $x$ is the source and $y$ is the sink in the flow network of the graph $G$ as $f_{x,y}$. I'm searching for a formal proof ...
user avatar
2 votes
1 answer
205 views

Proof that if the residual network of a max flow has no cycles then the max flow is 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$. After running Ford-Fulkerson algorithm a flow function $f$ returned ...
user avatar
0 votes
0 answers
104 views

How to solve a specific dining problem with max flow network?

n people named i are invited to a party. They are a(i) years old. We want to position them on some tables by obeying the following criteria: Each guest must sit around a table. Each table should have ...
user avatar
0 votes
1 answer
78 views

How to find the maximum number of square groups in a board

I'm stuck with the following problem: Given an n*m board, find the maximum number of square groups that can be positioned on the board. What are square groups? They contain 4 distinct squares named: ...
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
0 votes
0 answers
30 views

Min cut with smallest number of edges [duplicate]

Cormen's Algorithms 3rd edition Exercise 26.2-13 Page 731: Suppose that you wish to find, among all minimum cuts in a flow network G with integral capacities, one that contains the smallest number of ...
user avatar
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
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
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
0 votes
1 answer
250 views

How are vertex capacities defined in a flow network?

I'm new to network flows and I'm reading this topic from Cormen's Algorithms book (3rd edition) from 26 chapter. I came across this problem from the 26.1 section Suppose that, in addition to edge ...
user avatar
0 votes
0 answers
15 views

Inverse Weighted Flow Graph using Ford Fulkerson from T to S

As part of a class assignment I am given this problem: Given a Weighted Flow Graph N(G(V,E),s,t,c) and a flow function f. F is the max flow in the network. If s and t are flipped (The graph is now N'(...
user avatar
0 votes
0 answers
50 views

How to solve min cost perfect matching problems?

I'm trying to design an algorithm for the following generalized assignment problem. We converted the problem to a weighted bipartite graph constituted of two sets $A$ and $B$ where $|A| \ne |B|$. Any ...
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
0 votes
1 answer
48 views

Edmonds-Karp shortest path vs largest bottleneck

Depending on where I look, some places (https://courses.engr.illinois.edu/cs473/sp2009/notes/19-maxflowalgs.pdf) describe EK algorithm as choosing the st path with ...
user avatar
  • 151
0 votes
1 answer
198 views

Which one of the following is NOT a function of transport layer?

A. routing B. flow-control C. congestion control D. All of the above My guess is flow-control only because routing and congestion is part of the network layer. The network layer is the third later and ...
user avatar
1 vote
1 answer
47 views

Assigning balls to bins with constraints

Let $S= \{ b_{11}, b_{12}, b_{21}, b_{22}, b_{31}, b_{32},\dots, b_{n1}, b_{n2} \}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \{ B_1, B_2, \dots, B_m\}$ be a set of $m$ bins with ...
user avatar
  • 115
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
2 votes
1 answer
56 views

Edmonds-Karp bound doesn't seem to be tight

The proof that the Edmonds-Karp algorithm will require at most $O(|V||E|)$ uses the fact that when an augmenting path has critical edge $(u, v)$, $\delta_f(u)$ strictly increases. Therefore, that ...
user avatar
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
0 votes
0 answers
28 views

What is a net flow?

I tried to find strict definition in Google and books, but didn't succeed. How it connected with max flow and residual network?
user avatar
  • 131
1 vote
1 answer
20 views

Tiny question on residual networks

Is it true, that the number of edges in residual network is always less than twise the number of edges in the original flow network? My thoughts, that it's false, because in residual network quantity ...
user avatar
  • 131
0 votes
0 answers
16 views

Min-cut Max-flow problem: not obvious min-cut

I'm trying to find max-flow of such flow network: It seems to be 5, but how to prove it using the min-cut? I can't see any min-cut, which have a value of 5. I also heard in one video, that in min-cut ...
user avatar
  • 131
0 votes
1 answer
100 views

data transfer minimization problem

You have $2$ computers denoted by $C_1$ and $C_2$ and $n$ missions $M_1,M_2, \dots M_n$. Doing the $i$-th mission on $C_1$ (resp. $C_2$) costs $a_i$ (resp. $b_i$). Moreover if you do $M_i$ and $M_j$ ...
user avatar
0 votes
1 answer
69 views

Decide if the edges of a mixed graph can be directed in order to be an Eulerian Graph

I'm very stuck with this problem. Given $G = (V, E, A)$ a mixed graph where every edge in $E$ is directed and every edge in $A$ is undirected. Thinking as a max-flow problem, decide if it's possible ...
user avatar
1 vote
1 answer
22 views

Algorithm for shorthest path that contains exactly n edges of weight 2 in 1,2-weighted directed graph

I am trying to find an efficient algorithm for the following problem: Input: weighted directed graph G=(V, E) in which all edges are weigthed either 1 or 2 s,t ∈ V n ∈ N Output shortest path from s ...
user avatar
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
1 vote
0 answers
56 views

How to find all minimum cuts in network flow [duplicate]

In a network flow graph, using the Ford–Fulkerson algorithm, we can find a residual graph G_f which no augmenting paths. This gives us a way of finding one minimum ...
user avatar
2 votes
1 answer
189 views

Minimizing flow on a 2D matrix network

I am currently dealing with a problem that I believe to be a network flow related problem, and I am trying to find some similar solved problems to help me formulate my solution. I want to make it ...
user avatar
  • 21
1 vote
1 answer
708 views

What happens when we increase or decrease capacities in the minimum flow?

I am confused from these 2 true-false questions on the max flow and am seeking clarity on the basics. If in a network we increase the capacity of an edge in the minimum cut, the maximum flow gets ...
user avatar

1
2 3 4 5
7