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
44 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. ...
user avatar
1 vote
0 answers
11 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 ...
user avatar
  • 111
1 vote
1 answer
108 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 $...
user avatar
  • 11
2 votes
1 answer
71 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 ...
user avatar
2 votes
0 answers
37 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 ...
user avatar
  • 149
0 votes
0 answers
23 views

Important cuts bound

Important $(X,Y)-cut$ is defined as follows: S is an important $(X,Y)-cut$ if it is inclusion-wise minimal and there is no $(X,Y)-cut$ $S'$ with $|S′|<=|S|$ such that $R′⊃R$ where R,R' are the sets ...
user avatar
2 votes
1 answer
50 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 ...
user avatar
1 vote
0 answers
131 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 ...
user avatar
1 vote
2 answers
110 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 ...
user avatar
1 vote
0 answers
76 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$...
user avatar
1 vote
0 answers
61 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'$ ...
user avatar
  • 364
0 votes
1 answer
95 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 ...
user avatar
2 votes
2 answers
101 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 $...
user avatar
  • 364
3 votes
1 answer
62 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 ...
user avatar
  • 443
1 vote
0 answers
279 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 ...
user avatar
2 votes
1 answer
61 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 ...
user avatar
  • 1,615
1 vote
1 answer
62 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 ...
user avatar
  • 11
0 votes
0 answers
36 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 $(...
user avatar
  • 202
1 vote
1 answer
65 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'...
user avatar
  • 11
1 vote
1 answer
588 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-...
user avatar
  • 13
1 vote
0 answers
36 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 ...
user avatar
1 vote
0 answers
64 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 ...
user avatar
  • 111
1 vote
1 answer
350 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-...
user avatar
  • 137
2 votes
1 answer
408 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 ...
user avatar
4 votes
1 answer
1k 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 ...
user avatar
  • 317
3 votes
2 answers
589 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 ...
user avatar
  • 165
3 votes
1 answer
168 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.
user avatar
4 votes
0 answers
58 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 ...
user avatar
  • 4,009
0 votes
0 answers
261 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,...
user avatar
7 votes
1 answer
5k 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'...
user avatar
  • 235
3 votes
1 answer
185 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, ...
user avatar
2 votes
2 answers
733 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 ...
user avatar
1 vote
1 answer
49 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$ ...
user avatar
  • 936
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 ...
user avatar
  • 121
1 vote
1 answer
29 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 ...
user avatar
2 votes
1 answer
209 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. ...
user avatar
0 votes
1 answer
79 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 ...
user avatar
-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)...
user avatar
1 vote
1 answer
2k views

Given max-flow determine if edge is in a min-cut

We were given an exam question of: Given a flow network G=(V,E) with integer edge capacities, a max-flow f in G, and a specific edge e in E, design a linear time algorithm that determines whether or ...
user avatar
0 votes
1 answer
59 views

If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?

My problem is mainly from this lecture notes on convex optimization here page4 Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer ...
user avatar
  • 153
0 votes
0 answers
685 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 ...
user avatar
  • 133
1 vote
0 answers
198 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} \...
user avatar
  • 287
-2 votes
1 answer
813 views

Hackerearth practice problem not able to understand

I am not able to understand below problem, mainly the example. I have tried to ask explanation in their website but not received help yet. how they are calculating 36 and 43? and why 36+43 = 30$ is ...
user avatar
1 vote
1 answer
392 views

Minimum number of cuts to divide a rectangle

We're given a big rectangle, and a list of small rectangles contained inside it, with their vertex coordinates. We want a list of the minimum number of lines defined by a pair of points (x,y) that ...
user avatar
1 vote
0 answers
97 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 ...
user avatar
  • 121
1 vote
1 answer
535 views

a cut containing exactly one edge in each path

Given a digraph with a source $s$ and target $t$, must there be an edge cut which contains exactly one edge in every path from $s$ to $t$? I'm not interested in a minimum cut; any cut would do. If ...
user avatar
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 ...
user avatar
  • 31
0 votes
0 answers
231 views

How to uniquely determine a min-cut? [duplicate]

There are possibly several min-cuts for the source and target nodes of a graph. I think I can determine the same min-cut for the same graph by putting the following restriction "if there are ...
user avatar
  • 1,042
2 votes
0 answers
489 views

Algorithm for finding cut vertex and bridge in directed graph [closed]

In un-directed graph it is easy to find cut vertex and bridge but in directed graph removing cut vertex/bridge must increase number of strongly connected componenets.
user avatar
2 votes
1 answer
229 views

Max flow not min cut?

I understand the relation between max flow and min cut, however I made this (simplified) graph, and I cant figure out why max flow seems to be different from my min cut. Im probably overlooking ...
user avatar
  • 23