All Questions
Tagged with max-flow or network-flow
379 questions
1
vote
1
answer
70
views
Graphs — Remove the node that minimizes flow
I have a connected graph, each edge weight represents the maximum flow through that edge. I have a defined sink and source. I want to find out the node that should be removed in order to minimy flow ...
3
votes
1
answer
138
views
Can the Ford-Fulkerson Algorithm Guarantee Absolute Constant Approximation Without Back Edges?
I've been struggling with this homework question where the Ford-Fulkerson algorithm is modified to remove reverse edges from the residual graph. I tried to disprove that this approach can guarantee an ...
- 65
1
vote
0
answers
40
views
Counter example for an algorithm to decide if flow network has unique min-cut
Let N=(G,s,t,c) flow network and let m be the number of nodes in the network. given a max flow ...
0
votes
0
answers
52
views
Forward-Edge-Only Algorithm
I came across this interesting theoretical CS problem regarding max-flow networks in Algorithm Design (Kleinberg Tardos 2005):
The Forward-Edge-Only algorithm, which finds $s-t$ paths using only ...
- 1
1
vote
0
answers
15
views
Why does packet arrival increases increases exponentially when sending rate goes to link capacity?
This is from kurose and ross pdf's page 302 - 304. no error recovery (for example, in retransmission), flow control, or congestion control is considered in this case.
So what is the reason for ...
0
votes
0
answers
13
views
Decreasing flow by $\sigma << |V|$ [duplicate]
Let $G=(V,E,c,s,t)$ a flow network where $\forall e \in E: c(e) \in \mathbb{N}$. Assume we have $n$ vertices and $m$ edges. Let $f$ a max flow in $G$. Let $e=(u,v) \in E$, and let $\sigma \in \mathbb{...
- 169
0
votes
0
answers
10
views
Why does it satisfy the definition of a subgradient vector in a flow network problem
Hello everyone, I need to clarify some doubts. I was reading the article 'Subgradient Optimization Methods in Integer Programming with an Application to a Radiation Therapy Problem.' This is my first ...
- 1
1
vote
1
answer
172
views
Can this Integer Linear Programming problem be solved in polynomial time?
I have $n$ binary variables, and $m$ constraints. Each constraint can be stated as: "exactly $b$ of the variables in $S$ are equal to 1", for some positive integer $b$ and subset of the ...
- 13
0
votes
0
answers
14
views
Calculating the most influential set of source nodes on a target node when a source node's signal is propagated
I am mainly posting for guidance, as I don't know where to start looking in order to solve the following problem:
Given a directed graph G with edge weights between 0 and 1. As well as a set of ...
- 1
1
vote
0
answers
38
views
MSOL framing of max-flow probem
Given a graph $G=(V,E)$ with edge capacities $c_e$ for each $e\in E$, a source $s\in V$ and destination $t\in V$, how do I frame the max-flow problem in MSOL?
- 555
2
votes
2
answers
61
views
Least interrupted max flow after removing K edges algorithm
Given a graph $G=(V,E)$ and $k < |E|$, identify $E' \subset E$ such that $|E'| = k$, so that the max flow in the graph $(V, E')$ is as large as possible.
Is this possible in polynomial time? Is any ...
- 387
3
votes
1
answer
137
views
Maximum network flow with few non-integral edges
Consider the following network:
$s\to a, s\to b$ with capacity $1.5$ each;
$a\to 1, a\to 2, a\to 3, b\to 1, b\to 2, b\to 3$ with infinite capacity each;
$1\to t, 2\to t, 3\to t$ with capacity $1$ ...
- 6,164
0
votes
1
answer
38
views
Edmonds-Karp shortest-path distance monotonicity
If the Edmonds-Karp algorithm is run on a flow network $G=(V,\ E)$ with source $s$
and sink $t$, then for all vertices $v \in V - \{s,t\} $, the shortest-path distance $\delta_f(s,v)$ in the residual ...
- 15
0
votes
0
answers
26
views
How can i allocate troops so as to maximize the number of bases conquered without going over a maximum time?
I have a set of bases which are connected by directed edges illustrating which bases can be attacked from any particular base. Bases have a health pool (ex: 1,000,...
- 1
0
votes
1
answer
82
views
P=NP? A reduction of CNF boolean satisfiability to the circulation problem in an undirected graph
The picture below shows how to reduce the Boolean Satisfiability problem in CNF to the circulation problem in undirected graph (see here).
As you can see, a[i] are ...
- 155
1
vote
1
answer
102
views
Constrained Maximum Flow Minimum Cost
Let $G=(V, E)$ be a directed network with a set $V$ of vertices and a set $E$ of edges. Two vertices are distinguished, $s,t$ which are the source and sink respectively. Each edge $(i, j)$ has an ...
7
votes
3
answers
158
views
Finding a set of edges $E$ such that every $s$-$t$-path contains at least 2 edges from $E$
Given an undirected graph $G$ and two vertices $s$ and $t$, i want to find a minimum set of edges $E$ in $G$ such that every (simple) $s$-$t$-path contains at least 2 edges from $E$.
Is this problem ...
- 153
1
vote
1
answer
142
views
Disconnection of a directed and weighted graph
Let $G = (V, E)$ be a directed weighted graph such that all the weights on the edges are positive.
In $G$, we have two nodes, $v$ and $u$, that have a path from $v$ to $u$.
The question asks to find a ...
- 191
1
vote
0
answers
94
views
Optimization of value over network flow from start to end node with constant function multiplier edges tractability
Our problem is similar to this, but it details various approaches we can make.
The problem also was formulated operation research, but got hit with numeric limitations.
...
- 111
0
votes
1
answer
106
views
Minimum flow in a flow network
Let $G = (V, E)$ be a flow network with a source $s$ and sink $t$.
However, the constraints are a bit different:
Conservation constraint is as usual.
For each edge $e \in E$, we have that the flow $f$ ...
- 191
1
vote
0
answers
107
views
Prove that Dinic's algorithm with scaling works in $O(nmlog(C))$
(Given a graph $G$ with $|V|=n,|E|=m, max(c(a,b))=C$ and with integer capacities)
Dinic's algorithm with scaling is defined the following way:
set $\Delta = C$;
run Dinic's algorithm, only allowing ...
- 11
1
vote
0
answers
25
views
Stable Flow Problem with one sided preferences
I'm currently working on a problem to come up with ideas to solve a stable flow problem but unlike the traditional stable flow problem where every node has preferences on its incoming and outgoing ...
- 11
1
vote
1
answer
67
views
Scheduling classes with lower and upper bounds on students and classes
I am struggling to solve the following excercise:
Design an assignment of a group of n students to m classes. Student i
should take a minimum of $l_i$, and a maximum of $u_i$ within a set C1
of ...
- 23
0
votes
0
answers
23
views
flow network, class and classroom matching
Problem:
given a set of classes and classrooms, then given a set M of pairs (a,b), which means it is valid assignment from class a to classroom b(ex:(c,2), (c,3), (d,2), means class c can be assigned ...
1
vote
1
answer
156
views
Cycle-cancelling algorithm, Minimum cost flow
I am studying the cycle cancelling algorithm for the minimum cost flow problem, and I can not understand the proof of the following:
If there no negative cost cycles then you have a minimum cost flow. ...
- 13
1
vote
0
answers
62
views
Assumption on SuccessiveShortestPaths
I read that one assumption for Successive Shortest Paths algorithm for computing the minimum cost flow problem is that every cost is non-negative.
I also read that this assumption can be removed with ...
- 31
1
vote
1
answer
214
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 this ...
- 11
1
vote
0
answers
45
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 ...
- 11
1
vote
0
answers
21
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
2
votes
1
answer
169
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 ...
3
votes
2
answers
684
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 ...
- 105
1
vote
1
answer
82
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 ...
- 13
0
votes
0
answers
28
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
1
vote
0
answers
264
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
0
answers
330
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
185
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. \...
- 13
2
votes
1
answer
182
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$" ...
- 123
2
votes
0
answers
23
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
78
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 ...
- 919
0
votes
1
answer
275
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, ...
- 3
1
vote
1
answer
24
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 ...
- 364
0
votes
0
answers
159
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
250
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 ...
- 285
1
vote
1
answer
183
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 ...
- 1,962
2
votes
1
answer
98
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} ...
0
votes
1
answer
269
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 ...
1
vote
0
answers
221
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,...
- 136
1
vote
0
answers
96
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
285
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 ...
- 367
1
vote
3
answers
3k
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 ...
- 367