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
6 votes
2 answers
3k views

Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut ...
user avatar
  • 406
6 votes
2 answers
972 views

Finding a subset in bipartite graph violating Hall's condition

We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are ...
user avatar
  • 187
19 votes
5 answers
17k views

Maximum Independent Set of a Bipartite Graph

I'm trying to find the Maximum Independent Set of a Biparite Graph. I found the following in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow": Problem: ...
user avatar
7 votes
1 answer
5k views

Minimum-cut with minimum number of edges

I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph. Firstly, let'...
user avatar
  • 235
4 votes
1 answer
4k views

Algorithm for solving incremental max flow problem

I am working on a project where I need to be able to compute the maximum flow between two nodes in a graph after one of the edge weights has been incremented or decremented by 1. The graph is directed ...
user avatar
9 votes
1 answer
9k views

Effect of increasing the capacity of an edge in a flow network with known max flow

I need your help with an exercise on Ford-Fulkerson. Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance. Now suppose you are given an ...
user avatar
1 vote
1 answer
168 views

Determine whether a flow can satisfy node demands in a directed acyclic graph

I have the following problem that I'm unsuccessfully trying to solve: I have a directed graph with node demands. Unlike circulation with demands, these node demands do not "subtract" from the flow - ...
user avatar
  • 125
6 votes
2 answers
217 views

Integral solutions to circulation problem

Suppose we have a circulation problem (with only one commodity), where all lower bounds, upper bounds, and costs are integers. Are we guaranteed that if there is a solution, then there is an integral ...
user avatar
  • 143k
3 votes
1 answer
744 views

"Minimum" maximum flow with extra capacities

Problem: Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, ...
user avatar
9 votes
1 answer
11k views

How to find max flow in a graph after decrementing an edge capacity?

We're given a graph $G=(V, E)$, with source $s$ and sink $t$, $s\neq t$, and that all capacities are non-negative integers. Also the max flow itself is given, so we receive the value of max flow for ...
user avatar
  • 517
2 votes
1 answer
241 views

Network flow - minimum flow through edge [duplicate]

In my max flow network, I would like to have an edge with upper bound of the flow (a.k.a. edge capacity) $c_{max}$. However, I would also like to add a lower bound for the flow through the edge, $c_{...
user avatar
  • 163
0 votes
0 answers
189 views

Max flow but distribute evenly among candidate vertices

The max-flow algorithm finds the maximum flow through a graph given edge capacities. However, if there is an option between flowing through two edges, it will typically just leverage one of those ...
user avatar
19 votes
1 answer
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 ...
user avatar
  • 143k
18 votes
2 answers
1k views

Compute a max-flow from a min-cut

We know that computing a maximum flow resp. a minimum cut of a network with capacities is equivalent; cf. the max-flow min-cut theorem. We have (more or less efficient) algorithms for computing ...
user avatar
  • 71k
8 votes
4 answers
1k views

XOR-like behavior in flow networks

XOR is not the correct name, but I am looking for some kind of exclusive behavior. I am currently solving a set of different (assignment) problems by modeling flow networks and running a min-cost-max-...
user avatar
1 vote
2 answers
207 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 ...
user avatar
  • 491
11 votes
4 answers
30k views

How to find a minimum cut of a network flow?

I am currently reading the lecture slides from Princeton regarding network flows but I cannot understand how they manage to find out minimum cuts from a directed graph. Could someone explain how to ...
user avatar
4 votes
2 answers
2k views

maximum flow with all or nothing through each edge

Consider a maximum flow problem, where each edge has a small integer capacity. Now, I want a solution that for each edge uses the entire capacity, or no flow through that edge at all. To avoid the ...
user avatar
2 votes
1 answer
205 views

Proof that if the residual network of a max flow has no cycles then the max flow is 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$. After running Ford-Fulkerson algorithm a flow function $f$ returned ...
user avatar
5 votes
3 answers
1k views

Maximum number of matched vertexes in a one-to-many bipartite graph

I have a variant of bidding problem at hand. There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who ...
user avatar
3 votes
1 answer
1k views

Ford-Fulkerson Algorithm not "pushing back" flow

I am told that with every flow network, the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges (i.e. never “pushes back” the flow on any of ...
user avatar
2 votes
1 answer
939 views

Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths

Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut (...
user avatar
2 votes
0 answers
282 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 ...
user avatar
1 vote
1 answer
467 views

Maximum flow with maximum flow on specific edge

I am trying to solve the following problem: We're given a network flow $(V,E,c,s,t)$ and an edge $(u,v)$. We have to provide an algorithm that computes the maximum flow which has maximum flow on $(u,...
user avatar
1 vote
1 answer
4k views

What is a reducible flow graph?

What is a reducible flow graph? sorry if this is a stupid question but I'm having trouble finding an answer. Also multiple equivalent definitions and some motivation would be nice too.
user avatar
  • 83
1 vote
1 answer
962 views

Minimal set of rows and columns covering all non-zero entries in matrix

Given a matrix $A \in \{0,1\}^{n \times n}$, use network flows to describe an algorithm that finds the minimal set $I$ of rows and columns such that any non-zero entry is in one of the rows or columns ...
user avatar
  • 19
0 votes
0 answers
314 views

What's the relationship of max-flow-min-cut and Markov Random Fields?

I am trying to follow this paper [1]. There is a relationship between Markov Random Fields (MRF) to max-flow-min-cut. An MRF can be represented as an undirected graph, and you can find flow through it,...
user avatar