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
2answers
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 ...
6
votes
2answers
885 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 ...
19
votes
5answers
16k 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: ...
7
votes
1answer
4k 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'...
4
votes
1answer
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 ...
9
votes
1answer
8k 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 ...
1
vote
1answer
139 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 - ...
6
votes
2answers
180 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 ...
3
votes
1answer
729 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, ...
9
votes
1answer
9k 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 ...
2
votes
1answer
142 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_{...
0
votes
0answers
115 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 ...
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 ...
18
votes
2answers
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 ...
8
votes
4answers
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-...
1
vote
2answers
205 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 ...
4
votes
2answers
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 ...
11
votes
4answers
28k 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 ...
5
votes
3answers
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 ...
3
votes
1answer
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 ...
2
votes
0answers
273 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
1answer
895 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 (...
1
vote
1answer
371 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,...
1
vote
1answer
3k 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.
1
vote
1answer
900 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 ...
0
votes
0answers
292 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,...