Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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

Filter by
Sorted by
Tagged with
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 ...
Joseph Ritcher's user avatar
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?
Yandle's user avatar
  • 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 ...
Uri Greenberg's user avatar
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 ...
Matthieu Latapy's user avatar
4 votes
1 answer
304 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. ...
Erel Segal-Halevi's user avatar
3 votes
2 answers
131 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 ...
Ike348's user avatar
  • 131
0 votes
1 answer
197 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, ...
waxyao's user avatar
  • 3
0 votes
0 answers
172 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 ...
Yarin's user avatar
  • 275
2 votes
1 answer
84 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} ...
Green Ideology's user avatar
0 votes
1 answer
222 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 ...
Green Ideology's user avatar
1 vote
0 answers
120 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,...
Nadav's user avatar
  • 136
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 ...
Aishgadol's user avatar
  • 355
1 vote
2 answers
160 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 $$\...
Aishgadol's user avatar
  • 355
1 vote
0 answers
66 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 ...
user1246462's user avatar
0 votes
0 answers
200 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. ...
Prboetic's user avatar
1 vote
0 answers
24 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 ...
Aphyd's user avatar
  • 111
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 $...
Riem's user avatar
  • 11
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 ...
Mohamad S.'s user avatar
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 ...
NiRvanA's user avatar
  • 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 ...
user170383's user avatar
3 votes
0 answers
547 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 ...
Andrew Bell's user avatar
1 vote
2 answers
337 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 ...
curiouscupcake's user avatar
1 vote
0 answers
231 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$...
Vladis Becker's user avatar
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'$ ...
taktoa's user avatar
  • 364
0 votes
1 answer
190 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 ...
Amit wadhwa's user avatar
2 votes
2 answers
125 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 $...
taktoa's user avatar
  • 364
3 votes
1 answer
91 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 ...
spektr's user avatar
  • 453
1 vote
0 answers
633 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 ...
AsaridBeck91's user avatar
2 votes
1 answer
131 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 ...
abc's user avatar
  • 1,645
1 vote
1 answer
180 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 ...
TomLV's user avatar
  • 111
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 $(...
errorcodemonkey's user avatar
1 vote
1 answer
132 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'...
Bolek's user avatar
  • 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-...
Bhaskar's user avatar
  • 13
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 ...
Victor Hugo's user avatar
1 vote
0 answers
92 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 ...
Navin's user avatar
  • 111
1 vote
1 answer
636 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-...
BOB123's user avatar
  • 147
2 votes
1 answer
757 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 ...
idontevenknow's user avatar
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 ...
giorgioh's user avatar
  • 317
3 votes
2 answers
1k 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 ...
eatfood's user avatar
  • 195
3 votes
1 answer
310 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.
42069walrus's user avatar
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 ...
usul's user avatar
  • 4,129
0 votes
0 answers
380 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,...
AutoEncoder's user avatar
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'...
Donald's user avatar
  • 255
3 votes
1 answer
310 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, ...
Yoav Ben Haim's user avatar
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 ...
Shuvam Shah's user avatar
1 vote
1 answer
56 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$ ...
einpoklum's user avatar
  • 975
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 ...
Scoobie's user avatar
  • 121
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 ...
allrtaken's user avatar
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. ...
Hemispherr's user avatar
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 ...
Adi Lapp's user avatar