# Questions tagged [graph-cut]

The tag has no usage guidance.

5 questions
67 views

### Random Optimization on Graphs: Minimum Cut

Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...
29 views

### Karger's algorithm randomized min cut - probability of not contracting a particular edge

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 ...
133 views

### expected number of edges for fixed min cut

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$ ...
I am looking for examples/families of graphs with the following (maybe vague-sounding at first) property: the graph $G$ has a relatively large subgraph $B$ such that $B$ is bipartite-plus-a-few-edges ...