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
27
questions with no upvoted or accepted answers
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
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
0
answers
63
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
1
vote
0
answers
107
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
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
0
answers
20
views
flow network, class and classroom matching
Problem:
given a set of classes and classrooms, then given a set M of pairs (a,b), which means it is valid assignment from class a to classroom b(ex:(c,2), (c,3), (d,2), means class c can be assigned ...
0
votes
0
answers
14
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 ...
- 101
0
votes
0
answers
24
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 ...
- 634
0
votes
0
answers
145
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 ...
- 275
0
votes
0
answers
198
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
0
votes
0
answers
138
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
0
votes
0
answers
379
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,...
0
votes
0
answers
869
views
Separating a Graph into Two Components
I have an unweighted and undirected graph, and I want to divide this graph into two connected components by removing some vertices. The main objective is to minimize the number of vertices which must ...
- 133
0
votes
0
answers
1k
views
Is there a procedural way to find minimum s-t cut without guessing cuts?
I was reading about max flow theorem and there I saw scenario where the min s-t cut is found. But wherever I searched they did it after knowing the max flow or by guessing the cuts by iterating ...
- 31
0
votes
0
answers
197
views
Small LP for directed min cut?
Undirected min cut has a well known poly sized LP formulation by expressing the problem as one of finding a certain metric on the vertices minimizing the sum of distances on edges. Can this be ...
-2
votes
1
answer
2k
views
Please indicate whether each of the following statements is TRUE or FALSE and provide a brief justification
I provided my answers in the "answer your own question" bit.
I have applied the same logic for my answers to a&b and c&c which seem to be essentially the same questions. Am I right though?
a)...
- 31