Questions tagged [minimum-cuts]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
26 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 ...
0
votes
0answers
16 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 $(...
0
votes
0answers
29 views

Intuition behind Max Flow Algorithm

Given : A flow network G whose edges have capacity of 1 G's maximum flow |F| A positive integer K Delete exactly K edges so that the flow of the network is minimized. So I was asked to develop an ...
1
vote
1answer
25 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'...
0
votes
1answer
65 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-...
0
votes
0answers
32 views

Check if a pair of vertices belongs to the min-cut

Given a digraph $G = (V,A)$ with a source $s \in V$ and a sink $t \in V$, I need to adapt the graph to known if a pair of vertices $u \in V$ and $v \in V$ belongs to the min-cut $S$ between $s$ and $t$...
1
vote
0answers
33 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 ...
1
vote
0answers
46 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 ...
0
votes
1answer
71 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-...
2
votes
1answer
103 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 ...
4
votes
1answer
380 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 ...
3
votes
2answers
176 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 ...
3
votes
1answer
80 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.
4
votes
0answers
40 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 ...
0
votes
0answers
82 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,...
4
votes
1answer
2k 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'...
3
votes
1answer
118 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, ...
2
votes
2answers
270 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 ...
1
vote
1answer
40 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$ ...
2
votes
2answers
24 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
1answer
27 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 ...
2
votes
1answer
95 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. ...
0
votes
1answer
66 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 ...
-2
votes
1answer
877 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)...
1
vote
1answer
1k 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 ...
0
votes
1answer
40 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 ...
1
vote
0answers
42 views

For a minimum cut $(S, T)$, why do edges entering $S$ have a flow value of $0$?

I'm studying for an exam and I'm having trouble with a specific question: Let there be a flow network $G = (V, E)$ with a maximum flow $f$ and capacity $c$, a source $s \in V$ and a sink $t \in V$, ...
0
votes
0answers
533 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 ...
1
vote
0answers
179 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} \...
-2
votes
1answer
702 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 ...
1
vote
1answer
177 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 ...
1
vote
0answers
93 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 ...
1
vote
1answer
345 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 ...
0
votes
0answers
926 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 ...
0
votes
0answers
184 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 ...
2
votes
0answers
439 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.
2
votes
1answer
203 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 ...
5
votes
1answer
415 views

Min-cut in graph with demands/lower bounds

This week I read something about network flow from Algorithm Design. But I am confused about some concepts. We say, if a graph G contains some nodes with demands, positive or negative, how to define ...
2
votes
1answer
342 views

Karger's algorithm: why does every vertex have degree at least the number of edges crossing a min cut?

I'm currently watching a video on the analysis of Krager's Algorithm, and I am confused about something. The analysis goes as follows: Fix a min cut $(A,B)$. Let $k$ = # of edges crossing $(A,B)$ , ...
0
votes
0answers
186 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 ...
3
votes
0answers
38 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 "...