Questions tagged [graph-cut]

The problem of finding a k-edge connected spanning subgraph with the minimum number of edges is $ \mathcal{NP} $-hard in general. Is it the case for positive weighted graphs with "fractional ...

It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges. Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ ...

Given an undirected graph $G=(V,E)$, the max-cut problem asks for the partition $S_1,S_2\subset V$ , s.t., the number of edges going from $S_1$ to $S_2$ are maximized. Is it possible to maximize the ...

I know how Karger's algorithm works, and that the probability of finding a min-cut is over $1/n^2$. My question is the following. How can I find the probability of not contracting edges of a min-cut ...