Questions tagged [minimum-cuts]
A cut is a partition of a graph's nodes into two classes. Each cut is associated with a cut-set, the set of edges straddling the cut. For more, see: https://en.wikipedia.org/wiki/Minimum_cut https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm https://en.wikipedia.org/wiki/Karger%27s_algorithm
67
questions
9
votes
1
answer
9k
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'...
- 255
5
votes
1
answer
737
views
Min-cut in graph with demands/lower bounds
This week I read something about network flow from Algorithm Design. But I am confused about some concepts.
We say, if a graph G contains some nodes with demands, positive or negative, how to define ...
- 51
4
votes
1
answer
2k
views
find the union of all min cuts of a flow network
I'm trying to solve the following question :
Given a flow network $N = (G=(V,E),c,s,t)$. Let $\mathcal F$ be the set of all minimum cuts. Prove that $\mathcal F$ is closed under intersections and ...
- 317
4
votes
1
answer
291
views
Finding a minimum cut with an upper bound on the set sizes
In the (unweighted) minimum k-cut problem, the goal is to partition the nodes in a given graph to at least $k$ subsets, such that the number of edges between different subsets is as small as possible.
...
- 5,994
4
votes
0
answers
73
views
Karger's min-cut (contraction): Combinatorial argument for success probability?
The contraction algorithm for min-cut is: pick an edge $(u,v)$ uniformly at random, and "contract" it by merging $u$ and $v$ into a single vertex, deleting self-loops. Continue until two vertices ...
- 4,129
3
votes
1
answer
89
views
Karger's min cut and tips on bounding nonlinear recurrences
I was recently working on an old qualifying exam problem asking us to generalize Karger's randomized global min cut algorithm to that of a global min $k$-cut. I recalled the strategy of running a ...
- 453
3
votes
2
answers
989
views
Smallest $s$-component in mincut
Suppose there is a directed graph $G=(V,E)$, with source $s$ and sink $t$, and I compute the max flow on it. Then I know that I can find a min-cut $(A,B)$, by letting $A$ be the set of vertices that ...
- 185
3
votes
1
answer
306
views
is it possible to find the maximal min cut in polynomial time?
A maximal minimum cut is a minimum capacity cut with the largest number of edges.
- 31
3
votes
1
answer
303
views
Forcing an edge to be in S-T min-cut
Given a flow-network $N=(G,c,s,t)$ and an edge $e=(u,v)$, I am trying to build an algorithm that finds a minimum $(S,T)$ cut in the given network, that includes e.
So, I tried couple of steps, first, ...
3
votes
2
answers
116
views
Does there exist an algorithm / software that finds optimal graph partition while enforcing contiguity on a subgraph?
I am interested in the traditional graph partitioning problem, which roughly speaking seeks to obtain a partition of a graph into a number of components, in which each component has about the same ...
- 131
3
votes
0
answers
536
views
The Cut Lemma for graphs with non-distinct edges
In my introductory algorithms class I recently learned about the Cut Lemma and how it can be used to prove correctness for many Minimum Spanning Tree algorithms like Kruskal's and Prim's.
In class, to ...
- 57
3
votes
0
answers
51
views
Dominator tree with edges annotated by min-cut size
Consider the dominator tree of, say, the graph of objects in memory, computed by a memory profiler - one of the most powerful memory leak debugging features, I believe.
The dominator tree tells you "...
- 2,269
2
votes
1
answer
425
views
Karger's algorithm: why does every vertex have degree at least the number of edges crossing a min cut?
I'm currently watching a video on the analysis of Krager's Algorithm, and I am confused about something.
The analysis goes as follows:
Fix a min cut $(A,B)$.
Let $k$ = # of edges crossing $(A,B)$ , ...
- 383
2
votes
1
answer
92
views
Max-flow from a to c is at least the minimum of max-flow from a to b and max-flow from b to c
Given a directed weighted graph $G = (V, E, w)$, we refer to the max flow when $x$ is the source and $y$ is the sink in the flow network of the graph $G$ as $f_{x,y}$.
I'm searching for a formal proof ...
- 449
2
votes
2
answers
124
views
Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part
Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $...
- 364
2
votes
1
answer
731
views
Edmonds-Karp Algorithm with both directed and undirected edges?
How would this work and be implemented?
If you have directed edges pointing away from the source to a bunch of other verticies, and directed edges pointing from those vertices to a sink, but have ...
2
votes
2
answers
1k
views
How can maximum number of minimum cuts of a graph be exactly $n \choose 2$?
According to my instructor, $n\choose 2$ is the maximum number of minimum cuts we can have on a graph. To prove this, he showed the lower bound using an n-cycle graph. To prove the upper bound, he ...
- 121
2
votes
2
answers
25
views
Maximum Changes that don't Break the Build
Let's say I have a set of changes, e.g. replacing foo with bar in a codebase, how do I programmatically discover the largest set ...
- 121
2
votes
1
answer
83
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} ...
2
votes
1
answer
125
views
Properties of Gomory-Hu trees
Given an undirected graph $G=(V,E)$ a Gomory-Hu tree $T$ for $G$ has the following properties:
$T$ has a node for each vertex in the graph G and each edge in the tree corresponds to a minimum cut ...
- 1,625
2
votes
1
answer
352
views
Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?
For the proof of a maximum of (n 2) min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.
...
- 123
2
votes
1
answer
232
views
Max flow not min cut?
I understand the relation between max flow and min cut, however I made this (simplified) graph, and I cant figure out why max flow seems to be different from my min cut. Im probably overlooking ...
- 23
2
votes
0
answers
62
views
Size of the maximum matching in arbitrary graph
I am asked to find a probabilistic algorithm to determine the size of the maximum matching of an arbitrary simple undirected graph $ G $.
My claim is that, it is equivalent to find a global min cut on ...
- 159
2
votes
1
answer
96
views
important separators
Given a graph G and an important (X,Y)-separator S, why is it true that for every edge e in S the set of S\e is an important (X,Y)-separator in G\e
Important (X,Y) cut is defined as follows:
S is an ...
- 23
2
votes
0
answers
536
views
Algorithm for finding cut vertex and bridge in directed graph [closed]
In un-directed graph it is easy to find cut vertex and bridge but in directed graph removing cut vertex/bridge must increase number of strongly connected componenets.
1
vote
3
answers
2k
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 ...
- 355
1
vote
2
answers
334
views
Graph with $\Theta(2^n)$ minimum $(s, t)$-cuts
Is there any graph with $\Theta(2^n)$ minimum $(s, t)$-cuts?
Given an undirected graph $G = (V, E)$ and two distinct vertices $s$ and $t$ of $G$. A minimum $(s, t)$-cut is a $(S, T)$ cut of G which ...
- 304
1
vote
1
answer
633
views
Given a network flow find if there's a min cut that only one of the given edges lay on it
Given a network flow $G=(V,E)$ with capacity function $C$ source $s$ and hole $t$,
and given 2 edges $e_1 , e_2 $.
Find if there exists a min-cut such that only one of the edges belongs to the min-...
- 147
1
vote
2
answers
155
views
A graph is strongly connected iff every non-trivial cut contains an edge
As the title states, I am asked to prove that a directed graph $G=(V,E)$ is strongly connected iff for all non-empty subsets $\emptyset \neq S \subset V$, the cut
$\delta(S) \neq\emptyset$, where
$$\...
- 355
1
vote
1
answer
131
views
Can Stoer-Wagner find min s-t cut for given s and t?
Stoer-Wagner algorithm can be used to find global minimum cut in a graph. I'm wondering if it could be adapted to find a minimum s-t cut, given s and t. We can start a single phase with {s} but there'...
- 11
1
vote
1
answer
3k
views
Given max-flow determine if edge is in a min-cut
We were given an exam question of: Given a flow network G=(V,E) with integer edge capacities, a max-flow f in G, and a specific edge e in E, design a linear time algorithm that determines whether or ...
- 31
1
vote
1
answer
1k
views
All nodes reachable from source in residual network of any max flow are included in $S$ for any min-cut $(S,T)$
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$.
Also, we are given a max flow function $f$ on that network.
Let $...
- 11
1
vote
1
answer
175
views
Minimum cost of wood for woodworking project problem
This is a fun one, I really can't wrap my head around it. It's like an n-sum problem combined w/ a knapsack problem and I cant seem to find a solution.
I'm currently building a cabinet, and had just ...
- 111
1
vote
1
answer
1k
views
Number of minimum cuts in a graph
Situation :
I started watching Algorithm Lectures from Stanford University (Corsera). I stuck on one video lecture(https://www.coursera.org/lecture/algorithms-divide-conquer/counting-minimum-cuts-...
- 13
1
vote
1
answer
54
views
Set of DAG vertices disconnecting a vertex from forbidden vertices
Let $v$ be a vertex with in-degree 0 in an (acyclic) DAG $G$, and let $F$ be a subset of $G$'s vertices (the "forbidden") vertices. Now suppose $U$ is a set of vertices such that every path from $v$ ...
- 965
1
vote
1
answer
42
views
Is there an FPRAS for the number of min st cuts in general graphs?
Provan and Ball [1] showed that the problem of counting the number of minimum st cuts is #P-Complete. What is known about the problem of approximating the number of min st cuts? Is it possible to get ...
- 73
1
vote
1
answer
645
views
a cut containing exactly one edge in each path
Given a digraph with a source $s$ and target $t$, must there be an edge cut which contains exactly one edge in every path from $s$ to $t$? I'm not interested in a minimum cut; any cut would do.
If ...
- 11
1
vote
0
answers
106
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
65
views
Max flow in bipartite network where all vertices on the left hand side have degree exactly $2$
I have a flow question which I'm stumped on but seems like there should be an answer that I am not seeing.
Consider a network with a start $s$ and an end $t$ and a bipartite graph $L \cup R$. $s$ is ...
- 123
1
vote
0
answers
23
views
What are the locally optimal points in an LP formulation of the max flow problem?
I'm taking a grad level algorithms course and we just ended the course talking about linear programming, and we had previously talked about the max flow/min cut problem. Our professor said that the ...
- 111
1
vote
0
answers
222
views
Can the Global Minimum Cut problem for a directed graph be solved using the minimum s-t-Cut
I am using the following definition of the Global Minimum Cut problem:
Given a graph $G = (V,E)$, a Cut of $G$ is a partition of $V$ into two subsets $(A,B)$.
A cut-edge of $C$ is an edge $(u,v) \in E$...
1
vote
0
answers
67
views
What does a recursive min s,t-cut optimize?
Consider the following algorithm sketch:
Given an edge-weighted directed acyclic graph $G = (V, E, w : E \to \mathbb{N})$, adjoin a temporary source $s$ and sink $t$ to get $G' = (V', E', w')$. $G'$ ...
- 364
1
vote
0
answers
625
views
Finding s-t min-cut of undirected graph
Given an undirected graph with non-negative edge weights, and two vertices $s,t$ in the graph. I would like to find the minimal cut such that $s$ and $t$ are on different sides of the cut.
For example ...
- 111
1
vote
0
answers
39
views
Heuristic algorithm for the minimum weighted s-t cut with linear running time
To the best of my knowledge, the best algorithm for the minimum s-t cut in a weighted digraph is the Goldberg push-relabel algorithm with $O(n^{2}\sqrt{m})$ time complexity. I'm interested in solving ...
- 253
1
vote
0
answers
90
views
Minimum-cut with balanced and limited number of nodes in each partition: Does this have an efficient solution or even a name?
I'd like to remove the minimum number of edges from an undirected unweighted graph to partition the nodes into an arbitrary number of connected components $S_1$, $S_2$,$S_3$,... $S_k$ while maximizing ...
- 111
1
vote
0
answers
221
views
LP realaxation for multicut problem with polynomial number of constraints
The integer linear programming formulation for the multicut problem for the given graph $G = (V,E)$ and distinguished source-sink pairs of vertices $(s_1,t_1),...,(s_k,t_k)$ is:
\begin{alignat}{3}
\...
- 287
1
vote
1
answer
517
views
Minimum number of cuts to divide a rectangle
We're given a big rectangle, and a list of small rectangles contained inside it, with their vertex coordinates.
We want a list of the minimum number of lines defined by a pair of points (x,y) that ...
- 113
1
vote
0
answers
100
views
Minimum number of words to define any other
I'm interested in finding the minimum number of words needed to define some fraction (perhaps 95%) of the words occurring in an English dictionary (while ignoring the challenges of disambiguating ...
- 121
0
votes
1
answer
203
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 ...
0
votes
1
answer
88
views
Increasing the weights of all edges in an undirected graph makes a minimum cut still minimum
We have an undirected graph, with a weight function and a minimum cut. If you raise the weights of all the edges by one, the minimum cut remains minimal even with the new weights.
I know this is ...
- 37