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
68
questions
0
votes
0
answers
13
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?
- 101
0
votes
0
answers
26
views
Is the min-cut size of a directed graphs transpose the same as that of the original?
I was wondering whether the transpose of graph maintains the same size of the minimal cut in a directed graph (digraph).
This may be trivial as I haven't been able to find anything here or on Google ...
0
votes
0
answers
23
views
Sparsest cuts of planar graphs
Several algorithms for sparsest cut (and other kinds of balanced cuts) in planar graphs have been published, like for instance:
Finding minimum-quotient cuts in planar graphs, James K. Park, Cynthia ...
- 625
4
votes
1
answer
216
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,720
2
votes
2
answers
90
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 ...
- 121
0
votes
1
answer
98
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, ...
- 3
0
votes
0
answers
39
views
Minimum k-cut with equally weighted sets
I've got a weighted graph $G$, where additionally each vertex has a weight too. For a fixed, given $k$ I am looking for an algorithm to partition $G$ into $k$ disjoint sets of vertices, so that:
The ...
- 1
0
votes
0
answers
77
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 ...
- 229
2
votes
1
answer
73
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} ...
0
votes
1
answer
156
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
0
answers
79
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,...
- 126
1
vote
3
answers
1k
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 ...
- 315
0
votes
0
answers
45
views
Karger’s Min Cut algorithm: Cut after contraction is cut in original graph
Assume that Karger’s Min Cut algorithm is used on a graph $G=G_0=(V, E)$. Then, for $i>0$ let $G_i$ be the graph after the $i$th iteration of the Min Cut algorithm which is obtained by contracting ...
1
vote
2
answers
127
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
$$\...
- 315
1
vote
0
answers
63
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
0
votes
0
answers
124
views
Prove minimum vertex bisection problem is reducible from bisection width, thereby proving NP-Completeness
The bisection width problem gives you a yes or a no -> if there exists a bisection of size at most $K$ for $G=V,E$.
Minimum Vertex Bisection problem gives you a bisection of the smallest size.
...
- 1
1
vote
0
answers
17
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
1
answer
939
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
2
votes
1
answer
87
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 ...
- 453
2
votes
0
answers
57
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
82
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
409
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 ...
- 47
1
vote
2
answers
281
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 ...
- 294
1
vote
0
answers
184
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
66
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
0
votes
1
answer
170
views
Randomized algorithm for minimum cut
Given a simple undirected connected graph $G$, I want to find a min-cut
of $G$ using a randomized algorithm.
My attempt was to select a random edge in $G$ and reduce that edge to a
single vertex. And ...
- 49
2
votes
2
answers
118
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
3
votes
1
answer
85
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
1
vote
0
answers
527
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
2
votes
1
answer
117
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
1
vote
1
answer
157
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
0
votes
0
answers
113
views
Prove that there exists a minimum cut (S', T') where S' is the subset of S in which (S, T) is a minimum cut as well
I need to prove the statement $\exists$ a minimum cut $(S', T')$ where $S' \subseteq S$ for any minimum cut $(S, T)$
My attempt: Before proving this statement, I have a lemma if $(S_1, T_1)$ and $(...
- 202
1
vote
1
answer
89
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
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
0
answers
38
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
77
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
1
answer
609
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
2
votes
1
answer
657
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 ...
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
3
votes
2
answers
877
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 ...
- 175
3
votes
1
answer
264
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
4
votes
0
answers
69
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,099
0
votes
0
answers
346
views
Minimum-cut with Maximal number of edges
My question is: in a DAG, each edge has a different value of capacity, we can assume these capacities are integers multiples of the total number of edges. Also, sometimes we can have many minimum cuts,...
9
votes
1
answer
7k
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
3
votes
1
answer
272
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, ...
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
1
vote
1
answer
53
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$ ...
- 955
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
1
vote
1
answer
40
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
2
votes
1
answer
320
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