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
0 votes
0 answers
9 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?
Yandle's user avatar
  • 101
0 votes
0 answers
10 views

Finding max flow of an undirected graph where source and sink is connected

If I have an undirected graph with one source and one sink, but there's an edge (with finite capacity) between the source and sink, is the procedure to: Turn the undirected graph into a directed ...
Yandle's user avatar
  • 101
0 votes
0 answers
24 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) ...
CaptainHow's user avatar
0 votes
0 answers
12 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 ...
SUNITA GUPTA's user avatar
0 votes
0 answers
46 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 ...
TWhite's user avatar
  • 37
1 vote
1 answer
53 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. \...
Junyan Su's user avatar
2 votes
1 answer
60 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$" ...
qmww987's user avatar
  • 123
0 votes
0 answers
31 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 ...
SotirisD's user avatar
2 votes
0 answers
16 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 ...
Nicolás Maier's user avatar
1 vote
0 answers
29 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 ...
Mike Battaglia's user avatar
0 votes
1 answer
58 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, ...
waxyao's user avatar
  • 3
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 ...
Marik S.'s user avatar
  • 334
0 votes
0 answers
76 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 ...
scubadude22's user avatar
0 votes
0 answers
58 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 ...
Yarin's user avatar
  • 229
1 vote
1 answer
71 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 ...
Mohammad.Rostami's user avatar
0 votes
0 answers
37 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 ...
user157722's user avatar
2 votes
1 answer
54 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} ...
Green Ideology's user avatar
0 votes
1 answer
111 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 ...
Green Ideology's user avatar
0 votes
0 answers
46 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,...
Nadav's user avatar
  • 126
1 vote
0 answers
83 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 ...
Gabriel Rebello's user avatar
2 votes
1 answer
146 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 ...
Aishgadol's user avatar
  • 315
1 vote
3 answers
596 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 ...
Aishgadol's user avatar
  • 315
0 votes
1 answer
143 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 ...
Soha's user avatar
  • 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 ...
Legasee's user avatar
0 votes
0 answers
54 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 ...
Snowybluesky's user avatar
-1 votes
1 answer
225 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 ...
ConScience's user avatar
0 votes
0 answers
24 views

Maximize flow through a graph, where edges can be added subject to restrictions

I'm doing a course in algorithms and I'm stuck on this problem. Given a set of vertices on a grid. Every vertex has a coordinate (x,y). An source and a sink has ...
limeeattack's user avatar
2 votes
0 answers
44 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....
fuglede's user avatar
  • 165
1 vote
1 answer
157 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 ...
lchen's user avatar
  • 71
1 vote
1 answer
44 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 ...
AmacOS's user avatar
  • 13
0 votes
0 answers
28 views

Can the traffic relation between two nodes of a communications network be governed by an exponential law?

Disclaimer: This question was initially asked in Network Engineering SE, yet got closed due to its research nature. Assume a (hypothetical) communications network constituted by many nodes including ...
User's user avatar
  • 411
0 votes
0 answers
150 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 ...
Mehdi Saffar's user avatar
1 vote
0 answers
58 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 ...
user1246462's user avatar
0 votes
0 answers
64 views

A problem about min-cut on subgraphs

When I was trying to solve a problem, I met another problem like this: Given a undirected connected graph $G=(V,E)(|V|\le100)$ and some subgraphs of $G$: $G_1,G_2,\cdots,G_n(n\le 32)$, and all $G_i$ ...
Error_Yuan's user avatar
1 vote
0 answers
119 views

Finding maximum weight closure of a graph using min-cut

I am going through the book "Network Flows" by Ahuja et al. In chapter 19.2 "MAXIMUM WEIGHT CLOSURE OF A GRAPH", I find this example of turning a vertex-weighted (positive or ...
rhodeo's user avatar
  • 111
1 vote
1 answer
1k views

How to find a crticial edge in a flow network?

The complete question is as follows: An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. Give an efficient algorithm that ...
Jash Shah's user avatar
  • 111
1 vote
1 answer
80 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 ...
Sebastian Nielsen's user avatar
1 vote
1 answer
57 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-...
Danny Blozrov's user avatar
1 vote
0 answers
40 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 ...
AustinBest's user avatar
4 votes
0 answers
144 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 ...
Dmitry Kamenetsky's user avatar
1 vote
1 answer
65 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$ ...
Addem's user avatar
  • 313
-1 votes
1 answer
124 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
1 vote
0 answers
17 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 ...
Aphyd's user avatar
  • 111
1 vote
1 answer
93 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 ...
Gooby's user avatar
  • 141
1 vote
1 answer
597 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 $...
Riem's user avatar
  • 11
1 vote
1 answer
53 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 ...
NoamV's user avatar
  • 13
1 vote
0 answers
290 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 $...
dan paper's user avatar
1 vote
1 answer
82 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-...
Dan D-man's user avatar
  • 494
1 vote
1 answer
189 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 ...
HakolBeseder's user avatar
2 votes
1 answer
102 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 ...
Dan D-man's user avatar
  • 494

1
2 3 4 5
7