Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges.

Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick

Browse the full FOCS paper archive.