Skip to main content

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
11 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 ...
0 votes
1 answer
29 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 ...
1 vote
0 answers
36 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?
1 vote
1 answer
114 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 ...
0 votes
1 answer
86 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$ ...
3 votes
1 answer
83 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$ ...
2 votes
2 answers
44 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 ...
1 vote
1 answer
21 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 ...
1 vote
1 answer
742 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 ...
10 votes
2 answers
1k views

Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
2 votes
2 answers
200 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 ...
1 vote
1 answer
322 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) ...
0 votes
0 answers
22 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,...
8 votes
1 answer
346 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 ...
1 vote
1 answer
149 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 ...
16 votes
4 answers
2k 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 ...
5 votes
3 answers
3k views

Why in Flow network, there is no reversed edges?

I have read that Flow network is a directed graph, with no self loops and there is no reverse edges and non negative capacity. However in Residual network, we allow the reverse edges so we can cancel(...
7 votes
3 answers
146 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 ...
0 votes
1 answer
73 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 ...
1 vote
1 answer
84 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 ...
1 vote
1 answer
72 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 ...
1 vote
1 answer
88 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 ...
1 vote
0 answers
73 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. ...
1 vote
1 answer
65 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 ...
1 vote
1 answer
129 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. ...
1 vote
0 answers
81 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 ...
1 vote
0 answers
24 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 ...
0 votes
0 answers
20 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 ...
4 votes
2 answers
217 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. ...
1 vote
0 answers
60 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 ...
0 votes
0 answers
25 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
36 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 ...
1 vote
0 answers
20 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 ...
0 votes
0 answers
25 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 ...
2 votes
1 answer
84 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
665 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 ...
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 ...
0 votes
0 answers
15 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?
1 vote
0 answers
204 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) ...
1 vote
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 ...
0 votes
0 answers
46 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 ...
0 votes
0 answers
240 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 ...
1 vote
1 answer
163 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. \...
2 votes
1 answer
139 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$" ...
0 votes
1 answer
227 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, ...
2 votes
0 answers
21 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
67 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 ...
0 votes
0 answers
136 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
205 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 ...
1 vote
1 answer
161 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
2 3 4 5
8