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

67 questions
Filter by
Sorted by
Tagged with
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 ...
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
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 ...
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 ...
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. ...
• 6,016
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 ...
• 131
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, ...
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 ...
• 275
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} ...
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 ...
1 vote
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,...
• 136
1 vote
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
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 \...
• 355
1 vote
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 ...
• 123
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. ...
1 vote
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 ...
• 111
1 vote
1k views

• 364
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 ...
• 453
1 vote
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 ...
• 111
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 ...
• 1,645
1 vote
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 ...
• 111
138 views

• 975
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
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 ...
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