# 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
Filter by
Sorted by
Tagged with
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?
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 ...
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 ...
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. ...
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 ...
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, ...
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 ...
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 ...
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} ...
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 ...
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,...
1 vote
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 ...
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
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 \...
1 vote
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 ...
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 vote
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 ...
1 vote
939 views

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 ...
1 vote
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 ...
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 vote
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 ...
113 views

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 ...
1 vote