# 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
1 vote
130 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 ...
1 vote
951 views

1 vote
89 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-...
1 vote
276 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 ...
118 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 ...
1 vote
259 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 ...
324 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 ...
87 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 ...
922 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 ...
187 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 ...
105 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: ...
1 vote
643 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 ...
52 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 ...
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 ...
1 vote
72 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 ...
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....
1k 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 ...
1 vote
47 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, ...
112 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 ...
979 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 ...
1 vote
75 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 ...
1 vote
215 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 ...
116 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 ...
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 ...
46 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?
1 vote
26 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 ...
102 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$ ...
219 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 ...
1 vote
24 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 ...
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 ...
1 vote
61 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 ...
280 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 ...
1 vote
3k 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 ...
1 vote
200 views

### Multi Source/Sink Max Flow Alternative Reduction

When solving a multi source/sink max flow problem, the classic reduction to the single source/sink problem is to add a new source and sink node with infinite capacities that connect to/from the ...
178 views

### Assignment Problem with Minimum and Maximum constraints [duplicate]

I have the following problem: In a school, there are n students and m clubs, with n > m. Each student needs to be assigned a club. The students have preferences, (say top 3 or top 5) of the clubs ...
79 views

### Finding max flow in a undirected graph

According to this we can do so by replacing every edge in the undirected graph with two edges backwards and forwards with the same capacity. But I'm having a hard time seeing how this prevents ...
150 views

215 views

### Balanced Network max flow review

I would like a review for my algorithm for the following question: A flow network is a “balanced network” if for every $v∈V- {s,t}$ it holds that $c_in (v)=c_out (v).$ Let G be a balanced network in ...
119 views

### Properties of Gomory-Hu trees

Given an undirected graph $G=(V,E)$ a Gomory-Hu tree $T$ for $G$ has the following properties: $T$ has a node for each vertex in the graph G and each edge in the tree corresponds to a minimum cut ...
1 vote
27 views

### exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow

Given a network flow and there exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow. I've had this questions with ...
294 views

### Given an undirected graph, find an orientation such that every vertex has out-degree at least 3

Given an undirected graph $G=(V,E)$, describe an algorithm that computes an orientation of $E$ such that each vertex has out-degree at least 3. I know how to check if a vertex $v$ has at least $k$ ...
67 views

### why does relabel take O(VE) time total for unit capacity flow networks?

It is well known that for arbitrary flow networks, Goldberg's push-relabel algorithm takes $O(V^2E)$. Part of that comes from $O(V^2E)$ non-saturating pushes. Another part comes from $O(V)$ ...
1 vote
89 views

### Flow graph with non zero lower bound or 0 capacity

I am afraid the question title might not be sufficiently accurate but I could not come up with something more accurate Here is the problem Given 'n' machines Each machine has a set of capabilities ...
1 vote
Let there be a bipartite directed graph $G=(V,E)$. Let's say we have a path cover of the graph. In some texts it is said that this path cover "induces" a flow on $G$. What does this mean? ...