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.

104 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19
votes
1answer
1k views

Could min cut be easier than network flow?

Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
13
votes
2answers
771 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 ...
9
votes
1answer
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 ...
8
votes
0answers
227 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 ...
6
votes
0answers
1k views

A variation in Ford-Fulkerson algorithm

Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow. I was thinking that when we augment a path ...
5
votes
0answers
70 views

Network Reconstruction from Flow Function

Suppose that $T$ is a set of vertices in an unknown network. We have oracle $F(X,Y)$ that returns maximum flow value between $X, Y \subseteq T$ in the unknown network. Can we reconstruct the unknown ...
5
votes
0answers
592 views

Understanding Dinic's algorithm using dynamic trees

I have here a directed graph that I used to perform Dinic's algorithm to find maximum flow. I need to adjust this graph and this algorithm to work with dynamic trees (i.e. the Sleator-Tarjan algorithm)...
4
votes
0answers
66 views

Can we create the level graph from sink to source in Dinitz?

One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS. Could we create the level graph from sink to source ...
4
votes
0answers
149 views

Successive Shortest Paths vs Ford–Fulkerson

Can someone explain how exactly Successive Shortest Paths (SSP) is a generalization of the Ford–Fulkerson algorithm? I've found this stated in a few papers and websites as well as the Wikipedia page ...
3
votes
0answers
74 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....
3
votes
0answers
44 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 ...
3
votes
0answers
218 views

Introduction to the Traffic Light Scheduling Problem

I would like to understand the basics of how traffic light scheduling works. Looking through research papers the topics typically revolve around actual highway systems in urban areas, but also ...
3
votes
0answers
206 views

Efficient update to rational flow network?

Once we've computed the max flow in a flow network with integral capacities, we can change one of its edges' capacity by a unit and recompute a maxflow in linear time using BFS. Is there something ...
3
votes
0answers
1k views

Node potentials of minimum cost flow successive shortest path algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
2
votes
1answer
36 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 ...
2
votes
0answers
49 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 ...
2
votes
0answers
46 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 ...
2
votes
0answers
142 views

The max-min resource assignment problem

I am wondering if there are any results for the following max-min assignment problem: Given $n$ machines $C = \{C_1, C_2, \dots, n\}$ with the $k$-th machine has power $C_k$. There are $m$ tasks $T = \...
2
votes
0answers
33 views

Find a maximum flow that also maximizes the flow over a specific edge

Let $G=(V,E,c,s,t)$ be a flow-network, where $s$ is the source, $t$ is the target, and $c:E\mapsto [0,\infty)$ defines the capacity of every edge in the network. Let $e=(u,v)$ be an edge in the ...
2
votes
0answers
107 views

Add capacity to the uni-weighted graph to increase max flow

Given a uni-weighted graph G (in which each edge has the capacity of 1), and we have k extra capacities (k is an integer) that we can spend on any subset of existing edges. That is, we can increase ...
2
votes
0answers
31 views

FPTAS algorithm to find flow at each link for multi commodity flow problem?

Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the ...
2
votes
1answer
91 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. ...
2
votes
0answers
32 views

Transit scheduling using flow networks

I am studying the maximum/minimum flow question, and was given the following problem: A traveling agency has $n$ destinations on their service map, and it intends to maintain them with minimum ...
2
votes
0answers
72 views

Find optimal redistribution in flow graph

I have directed graph (maybe with cycles), and some resources in vertices (let's say gold). I can transfer gold between vertices only in direction of edges. The task is to minimize maximum value of ...
2
votes
0answers
139 views

long-lived scheduling using max-flow & push/relabel

I'm writing a scheduler of long-lived Processors which execute long-lived Tasks. Processors and Tasks may each come and go over time, at any time (when a Processor departs, its assigned Tasks now ...
2
votes
0answers
41 views

Card Shuffling, Bounding Mixing time using Paths and Flows

I've been struggling with a problem that is very similar to a 2014 question posted here. The question in particular is 3(1) and 3(2). To paraphrase, we are supposed to use paths and an encoding ...
2
votes
0answers
518 views

Bhandari Algorithm: Canceling Edges

I have a quick question on implementing the Bhandari algorithm. I do not have the textbook where the algorithm is originally given (Bhandari, Ramesh (1999). Survivable networks: algorithms for ...
2
votes
0answers
349 views

Minimal Separator / Vertex disjoint Paths

I'm in need of implementing the algorithm to actually locate the minimal vertex separators set of the whole graph (not just s-t). It is my understanding that this can be done by doing the s-t ...
2
votes
0answers
136 views

How to construct a network flow problem?

I have the optimization problem given below max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ s.t $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad 2)\quad x_{ij} \in {0,1}$ $\quad ...
2
votes
0answers
275 views

Complexity class of maximum flow problem with random arc capacity

Given a graph $G=(N,E)$ with a special source node $s$ and sink node $t$. There is a subset of arcs $E^* \subset E$ that has the capacity drawn from a probability distribution $F$ independently. Then ...
2
votes
0answers
185 views

Cheeger constant of a graph versus conductance of a Markov chain

Given some graph $G$ with vertices $V$ and edges $E$, its Cheeger constant $h(G)$ is well defined as $$ h(G) = \min_{S\subset V,0<|S|\leq|V|}\frac{|\partial S|}{|S|}. $$ Given some doubly-...
2
votes
0answers
668 views

How can we add back edges in Ford - Fulkerson algorithm?

I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent ...
2
votes
0answers
591 views

Does Edmonds Karp take back-edges into account?

I amb doubting with the implementation of the Edmonds-Karp implementation of the Ford-Fulkerson algorithm. This is a problem with flow networks. As I understand the algorithm, it consists on taking ...
2
votes
0answers
51 views

Distributed push relabel with changing graph topology

There is at least one (1) distributed version propsosed for the push-relabel maximum-flow algorithm. I wonder if and how this algorithm can cope with nodes leaving or enterig the graph during runtime. ...
2
votes
0answers
118 views

Max Flow on low depth DAGs

I have a family of acyclic networks in which every path from the source of a given network to its target has length exactly $3$. I'm aware of a publication that in general, finding a max flow in a DAG ...
2
votes
0answers
209 views

residual network for a network with lower and upper bounds?

How does one construct the residual network in such a case? The formula is for edge $(u, v)$ is $$rf(u,v) = (c_{\mathrm{upper}}(u,v) - f(u,v)) + (f(v,u) - c_{\mathrm{lower}}(v, u))\,,$$ where $rf(...
1
vote
1answer
18 views

Reducing a seating problem 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 ...
1
vote
1answer
68 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 ...
1
vote
0answers
63 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 ...
1
vote
0answers
29 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, ...
1
vote
1answer
50 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 ...
1
vote
1answer
68 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
0answers
52 views

Partially defined boolean function

Consider a Boolean function $f(x_{1}, x_{2}, \dots, x_{n})$. The value of $f$ is defined on some set of inputs, and some inputs are undefined (let us label undefined value with $?$). It is possible to ...
1
vote
1answer
61 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 ...
1
vote
0answers
24 views

Maximum edge-disjoint flow

Consider the case where you have two types of flow, let's say "red" flow and "blue" flow. You want to send $k_r$ red flow and $k_b$ blue flow through a DAG $G$ from a source $s$ to a sink $t$ in such ...
1
vote
0answers
34 views

Getting rid of negative-cost edges in min-cost max-flow algorithmically

I have a min-cost max-flow problem. The designed network (without cycles) gives correct results using cycle cancelling, but it is way too slow. I would like to get rid of negative edges so that I can ...
1
vote
0answers
141 views

Practice question on the applications of flows and cuts

This question is from Erickson's textbook on algorithms, p. 376, question 18. Faced with the threat of brutally severe budget cuts, Potemkin University has decided to hire actors to sit in ...
1
vote
0answers
54 views

Binary flow in max flow problem

is there a way ensure that there only is flow through vertices c and d and not e or through d and e and not c. But not both at the same time. With an simple extension it is possible to put also ...
1
vote
0answers
22 views

graph trend filtering results from different maxflow algorithm

We have followed the official code of the Graph trend filtering (GTF) https://arxiv.org/abs/1410.7690, and modified the code with Ford Fulkerson Algorithm (FFA) instead of parametric maxflow. The ...
1
vote
1answer
154 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) ...