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
13
votes
2
answers
1k
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 ...
CommunityBot
- 1
1
vote
1
answer
17
views
Max flow, min cost with upper and lower bounds
:)
I am trying to implement an algorithm that fairly distributes people into groups, given their ranking of those groups, while also taking into account their preference for partners.
I have modeled ...
D.W.♦
- 156k
-2
votes
0
answers
22
views
Maximum flow of multiples [closed]
The problem is that I'm given 3 numbers N which represents the number of nodes in my graph, M which reprensents the amount of vertexes and x which represents an amount of people. The problem is that I ...
- 1
0
votes
0
answers
16
views
maximum step of sorting network
How to calculate the maximum step of sorting network?
Based on image below, it has most comparators at second index which is 9 comparators than another indices. That's mean, overall networks need 9 ...
1
vote
0
answers
28
views
Lower bounds on max-flow and assignment problems
As far as I know, all existing strongly polynomial algorithms for flows and assignment problem have $\Omega(V^3)$ complexity in the arithmetic model (assuming the graph is dense). I'm interested in ...
D.W.♦
- 156k
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 ...
CommunityBot
- 1
1
vote
0
answers
16
views
epsilon-optimality in cycle-cancelling for min cost flow
I'm learning about the (min-mean) cycle-cancelling alg for min-cost flow in Ahuja, Magnanti, and Orlan's Network Flows book (Chapters 9 and 10). When talking about the alg, they prove this fact ...
- 21
0
votes
0
answers
13
views
Edge connectivity using flow network
Find an algorithm for edge connectivity in undirected graph using flow networks. Try to use $O(m)$ edges.
So basically the flow network should be used as a "helper function" and the graph ...
- 31
2
votes
1
answer
56
views
Dinitz’ algorithm in simple unit-capacity networks
I am studying for an algorithm design course, and can't understand this demonstration about how Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time.
This is what is written on the slides ...
- 15.5k
0
votes
1
answer
50
views
Finding min s-t cut of network with flow on the nodes
Given a network with flow on the nodes. How can we find min s-t cut in a network with flow on the nodes?
We know how to find min s-t cut whenever there’s a network with flow on the edges (Ford ...
CommunityBot
- 1
3
votes
2
answers
644
views
Find max total revenue in a directed graph
Problem:
Imagine you are an agent with a knapsack, who travels a known route of cities. All cities are different: $C_1 \rightarrow C_2 \rightarrow \dots \rightarrow C_n$. Each city offers you to buy ...
- 28.3k
0
votes
0
answers
25
views
Max flow with a minimal in-degree objective on certain nodes (for edges with non-zero flow)
The following a small-scale example meant to illustrate the general problem
Suppose we have $n = 60$ marbles that we want to distribute into 3 bowls, $B = \{bowl_1, bowl_2, bowl_3\}$
The marbles can ...
- 3
0
votes
0
answers
13
views
Can Gomory-Hu tree algorithm be applied to graphs with more than one connected component?
If I have an undirected graph with more than one connected component, can I apply the Gomory-Hu algorithm directly on the entire graph or do I have to apply it separately to each component?
- 101
1
vote
0
answers
78
views
Why in Edmonds Karp or Ford Fulkerson Algorithm the time complexity of BFS or DFS respectively is O(E) rather than O(V+E)?
For these algorithms, the time complexity of BFS and DFS is O(E).
I have gone through many websites and even the algorithm books, but I never got a clear idea of why it is O(E). It just says it's O(E) ...
- 11
0
votes
2
answers
1k
views
Confused with the proof that Edmonds-Karp always monotically increases the shortest-paths
The proof for the lemma from "Introduction to Algorithms by Cormen et. al." is not clear for me. I can't comprehend a few things. Here is a lemma and its proof. My questions are below.
The notation ...
- 3,678
1
vote
1
answer
15
views
Defining multi commodity flows as polytopes
In a multi commodity network, we define a demand to be a vector $d \in \mathbb{R}^{k}$, where $k$ is the number of pairs of sinks. That is, $k = \binom{S}{2}$, where $S$ is the set of sinks (aka ...
CommunityBot
- 1
1
vote
1
answer
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 ...
CommunityBot
- 1
0
votes
1
answer
276
views
Possible ways to have cross and full edges in a mincut maxflow
I am trying to solve the following problem about maxflow mincut
it seems like my conclusion is incorrect and I am wonder where.
There is no graph just following question.
An edge e can be (x) ...
CommunityBot
- 1
3
votes
1
answer
184
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. ...
CommunityBot
- 1
0
votes
0
answers
20
views
What is practical implication of Bandwidth delay product?
It's given that the bandwidth-delay product defines the number of bits that can fill the link; while the sender can send (1+(2 * Bandwidth * Delay)) units before getting acknowledged for the first ...
- 101
1
vote
1
answer
128
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 ...
CommunityBot
- 1
2
votes
1
answer
168
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 ...
CommunityBot
- 1
0
votes
0
answers
81
views
Best time to buy and sell stocks with multiple buy transactions are allowed and can sell all shares at once
I've been trying to solve a variation of this problem https://stackoverflow.com/questions/62389658/best-time-to-buy-and-sell-stocks-when-allowing-consecutive-buys-or-sells
You are given an input array ...
- 37
1
vote
1
answer
100
views
Solving shortest path with negative weights with linear program. What is the underlying problem we want to solve?
Let us consider a shortest path problem with weights $w_e$ for each edge $e$. It can be formulated as a (integer) linear program (ILP).
\begin{align}
\min \quad &\sum_{e \in E} w_e x_e \\
s.t. \...
- 5,827
2
votes
1
answer
76
views
How to reduce $k$-oriented problem to max flow problem?
Given an undirected graph $G$, how to reduce this problem :"Judge whether every edge of $G$ can be given a orientation such that for every vertex $v$ in $G$ has input-degree of at most $k$" ...
- 5,827
0
votes
0
answers
42
views
Minimum cost flow, handling antiparallel-double edges
In maximum flow if you have double(antiparallel) edges you just add an intermediate node and break the edge in two with the same capacity. In minimum cost flow you can do the same but break the cost ...
D.W.♦
- 156k
0
votes
1
answer
103
views
How to find the subsets S and T and the min-cut of this graph?
I get the residual graph by Ford-Fulkerson Algorithm:
I get that the minimum cut can be found by the residual graph, and when traversing this residual network from the source to all reachable nodes, ...
CommunityBot
- 1
2
votes
0
answers
17
views
Inverted Min Cost Max Flow
I'm starting to think there's no possible solution to this problem, but before jumping to conclusions I want to confirm it with collective knowledge.
Let's imagine that there's a 2D grid, where S ...
1
vote
0
answers
40
views
Networks and data flow - graph algorithms for propagating updates from nodes correctly
Suppose I have an acyclic directed graph of Nodes which subscribe to Events. When an Event callback is activated for some Node, the Node's internal update() method is called. Then, because the Node ...
- 837
0
votes
0
answers
99
views
Budgeted min cost max flow in bipartite where the flows must also be a matching set
I'm trying to find a problem description that is roughly akin to a budgeted min-cost max-weight bipartite matching where the capacities are greater than 1. Imagine a max-flow problem on a graph that ...
0
votes
0
answers
78
views
Network flow - properties of a vertex that belong to any minimum cut
while solving some questions about network flow I was wondering about the following statement:
Given a network flow (a graph $G=(V,E)$ with a source $s \in V$ and sink $t \neq s \in V$) > and an ...
- 229
1
vote
1
answer
107
views
Minimize bottleneck in flow network
Let $G=(V,E)$ be a flow network with two vertices $s,t$ also each edge has its capacity equal to $\infty$. Our goal is to transfer a flow of size $C$ from $s$ to $t$ so that minimize an edge that has ...
- 38.6k
0
votes
0
answers
64
views
Showing that the max-flow min-cut theorem holds for negative capacities as well
I want to show that the max-flow min-cut theorem still holds for a graph or network with non-positive capacities for edges as well. I was thinking I could just flip the edges and thereby flip the ...
2
votes
1
answer
73
views
Will the Ford-Fulkerson Algorithm always return the same min-cut for any source-sink from one side of the min-cut to the other?
I was playing around with https://visualgo.net/en/maxflow when I realized a pattern:
Take this graph, for example. We notice that the min-cut divides the graph into two sets of nodes: {0, 2, 3, 6} ...
- 38.6k
0
votes
1
answer
158
views
Finding the nodes in the source and sink side of a min-cut
We are learning of the Ford-Fulkerson Algorithm for max-flow/min-cut, and I have been wondering of the following question:
How do we exactly find which nodes are on the "sink" side of the ...
- 15.5k
0
votes
0
answers
80
views
Network Flow - qualities of saturated edges
While I know that every edge is fully saturated in every min-cut of a network flow, I'm trying to get some intuition when the converse is true.
I can find an example using edges with infinite capacity,...
- 126
1
vote
0
answers
88
views
Successive shortest paths with fixed costs and costs per unit
I have a directed graph $G(V,A)$ with arc costs $c_{ij} = \alpha_{ij}1_{x_{ij}>0} +\beta_{ij}x_{ij}$, where $\alpha_{ij}$ and $\beta_{ij}$ are, respectively, a fixed cost and a cost per unit of ...
- 111
2
votes
1
answer
164
views
Min-cut with maximal number of edges
I’ve searched for a solution for this problem for some time now, it is out of an algorithm question sheet.
We know that in order to find the minimal amount of edges in a flow graph’s min-cut we need ...
- 38.6k
1
vote
3
answers
1k
views
Decide whether a flow graph has a single min-cut
The problem is whether a graph (which we represent as a flow network) has a single min-cut, or there could be multiple min cuts with the same maximum flow value, I've yet to encounter a well explained ...
- 38.6k
0
votes
1
answer
191
views
A variation of the maximum bipartite matching problem
Given a bipartite simple graph $G=(V,E)$, where $V=A\cup B$ and $A\cap B=\emptyset$, any edge in $E$ connects two vertices in $A$ and $B$, respectively. The maximum bipartite matching problem is to ...
- 25
-1
votes
1
answer
32
views
Struggling to disprove this flow network question
Consider a flow network $G$. Let $(S, T)$ be a min-cut of $G$. Let
$(u, v)$ be an edge that crosses the cut from $S$ to $T$. Claim:
increasing the capacity of $(u, v)$ causes the value of the maximum
...
- 1
0
votes
0
answers
68
views
Can the airline scheduling algorithm (network flow) be extended to handle seating capacities?
The airline scheduling problem determines the minimum number of airplanes required to service a set of passenger flights, where a plane can service routes A$\rightarrow$B and C$\rightarrow$D if there ...
-1
votes
1
answer
402
views
Maximum Flow algorithm. How to prove the following statements
Good Evening,
So I am trying to solve this exercise which is a paticular case of maximum flow algorithm. Here the graph must have all even edges and 1 odd edge and it must have a maximum flow that is ...
- 12.5k
1
vote
2
answers
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 ...
- 15.5k
2
votes
2
answers
223
views
Literature on network-flow (optimization) approximation algorithms
I've been searching on literature on approximation algorithms in the context of network-flow problems (optimization) to finish my bachelor degree.
However, I have been looking in several well-known ...
- 165
2
votes
0
answers
51
views
State of the art implementations of minimum-cost multicommodity flow approximation algorithms
I'm looking for implementations of approximation algorithms (or algorithms that would be meaningful to implement for use in practice) for the minimum-cost multicommodity flow problem as defined in e.g....
- 165
1
vote
1
answer
215
views
Max-flow problem with additional constraint
Consider the max-flow problem with a set of additional constraints, each in the following form: the flow on edge $e$ must equal the flow on edge $e'$. My question is how to modify existng max-flow ...
- 15.5k
1
vote
1
answer
79
views
Can distance from source to any of the vertex decrease during the run of Ford Fulkerson algorithm?
During the run of Ford Fulkerson algorithm if we label each vertex with d(v) where it means the shortest path distance from source to vertex v in residual graph. Is it possible that for some vertex ...
- 12.5k
0
votes
0
answers
187
views
Network flow on multigraph easier than I thought?
I encountered many articles on max-flow problem that do not go beyond simple graphs in which two nodes are either connected with a single directed edge OR two nodes are connected with a single ...
- 101
1
vote
0
answers
63
views
Max flow in bipartite network where all vertices on the left hand side have degree exactly $2$
I have a flow question which I'm stumped on but seems like there should be an answer that I am not seeing.
Consider a network with a start $s$ and an end $t$ and a bipartite graph $L \cup R$. $s$ is ...
- 123