Asymptotically Optimal Linear Algorithm for the Minimum k -Cut in a Random Graph
Olivier Goldschmidt, Dorit S. Hochbaum · SIAM Journal on Discrete Mathematics · 1990
The k-cut problem is to find a partition of a graph into k nonempty components, such that the number of edges between components is minimum. A random graph in $\mathcal{G}_{n,p}$ is a simple graph on n vertices with each pair of vertices connected by an edge with probability p. It is proved that, when k is fixed, a k-cut of almost every graph from $\mathcal{G}_{n,p} $ consists of $k - 1$ isolated vertices and one component on the remaining $n - k + 1$ vertices. An important outcome of this property is a linear algorithm that derives the minimum k-cut in such graphs, almost certainly.