Optimal K-Cut Problem and Karger-Stein Algorithm
The Karger-Stein Algorithm is proved to be optimal for the K-Cut problem in graphs, efficiently cutting them into at least k components. This algorithm has been extensively researched and compared against various prior results and approaches, proving its effectiveness. By randomly contracting edges and partitioning the graph, it achieves the minimum cut with high probability, making it a leading solution in computational graph theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
The Karger-Stein Algorithm is Optimal for k-cut Jason Li Carnegie Mellon University slides by Anupam Gupta Based on joint work with: Anupam Gupta (CMU) and Euiwoong Lee (CMU NYU U.Michigan)
the k-cut problem Given graph G, delete minimum weight edges to cut graph into at least ? components. Think of ? as a large constant.
two examples Cycle ?? OPT = ? number of min-k-cuts = ? ? Complete graph ?? ? 1 2 ? ? 1 OPT = ? 1 ? 1 number of min-k-cuts = ?? Figure from Wikipedia: thanks Koko90!
k-cut Given graph G, delete minimum weight edges to cut graph into at least k components. Think of k as a large constant. The main questions: 1. (computational bound) How fast can we compute k-cut? 2. (extremal bound) How many minimum k-cuts are there?
prior results Given graph G, delete minimum weight edges to cut graph into at least k components. rand algo in ?(?2? 2) time det. algo in ?(??2? 2) time rand algo in ?(?1.99?) time for weighted graphs rand algo in ?(?(1+? 1 )?) time for unweighted graphs [Karger Stein 96] [Thorup 08] [Chekuri Quanrud Xu 18] [Gupta Lee L. 19] [L. FOCS 19] reduce (edge-weighted) k-clique to k-cut so solving k-cut exactly takes (?(1 ? 1 )?) time, doing better seems unlikely. Also, several 2-approximate algorithms, and seems difficult to do better than 2 ?
our results Given graph G, delete minimum weight edges to cut graph into at least k components. rand algo in ?(?2? 2) time det. algo in ?(??2? 2) time rand algo in ?(?1.98?) time for weighted graphs rand algo in ?(?(1+? 1 )?) time for unweighted graphs [Karger Stein 96] [Thorup 00] [Chekuri Quanrud Xu 18] [Gupta Lee L. 19] [L. FOCS 19] Theorem: Karger-Stein algo finds minimum k-cut in ??(??+?(1)) time! Note: Algo can enumerate all minimum k-cuts in the same time extremal bound too.
Kargers algorithm for minimum cuts Pick a random edge, and contract it. Stop when 2 vertices remain. Theorem: finds the mincut w.p. at least 1/? 2 Figure from Wikipedia: thanks Thore Husfeldt!
Karger-Stein algorithm for k-cuts Pick a random edge, and contract it. Stop when 2? vertices remain. Return a random partition of what remains. ? 2? ??(? 2 ? 1) Theorem: finds the mincut w.p. at least 2 2?/ Proof: when r vertices remain, probability to contract an edge in OPT is ??? #edges (? average of all ? degrees)/2 2(? 1) ? ? 1 average of smallest ? 1 degrees Pr[OPT survives contraction] (1 2 ? 1 ) exp( 2 ? 1 ??) ? 2(? 1) ?
what about the two examples? Cycle ?? ??? ? ? 2(? 1) ? => ?? time #edges= Complete graph ?? ??? ? 1 ? ?2/2= 2(? 1) ? #edges tight! How to beat ?2(? 1)? Key Idea: after a while, most vertices degree 2n
theorem and proof idea Theorem: Karger-Stein outputs any fixed minimum k-cut with probability ?(? ? ?(1)). Proof outline: Define ??=??? ?. 1. refined analysis of the Karger-Stein randomized algorithm If G has only linearly many small cuts, then K-S behaves better. 2. connection of cuts in graphs to extremal results about set systems 1?? ? # small cuts with size in [??, 2 ? ??] at most ? +
a continuous view Imagine each edge has exponential clock with rate 1/?? I.e., fires independently w.p. ?/?? in any infinitesimal interval ? When an edge fires, contract it. Claim: the edges are contracted in random order (so we re running K-S). But now events in each ? timestep are independent (and more than one event happens with essentially zero probability as ? 0).
a continuous view Imagine each edge has exponential clock with rate 1/?? I.e., fires independently w.p. ?/?? in any infinitesimal interval ? When an edge fires, contract it. If ? vertices remain at any time 1. have at least ? ??/2 edges in the graph 2. contract at least ?/?? ? ??/2= ??/2 edges in expectation 3. if ? 0, this is like contracting ??/2vertices (no cycles contracted) 4. so ? decreases by at least (1 Fact ?: after ? time, expected number of vertices is at most ? 1 2) factor in ? time ? ?/?= ?? ?/2 ? 2
a continuous view Imagine each edge has exponential clock with rate 1/?? I.e., fires independently w.p. ?/?? in any infinitesimal interval ? When an edge fires, contract it. Fact ?: after ? time, expected number of vertices is at most ?? ?/2. So we stop at time at most ? = 2ln?. ?/?= ? ??. Fact 2: a fixed min-k-cut survives for ? time w.p. 1 ??? ?/?? This is ? 2? at time ? . Essentially the K-S analysis: any min-cut survives w.p. ? 2? when down to ?(?) vertices.
a continuous view Imagine each edge has exponential clock with rate 1/?? I.e., fires independently w.p. ?/?? in any infinitesimal interval ? When an edge fires, contract it. Suppose only ?(?) small cuts of size in [??, 2 ? ??]. (clique: small cuts = singletons) ?/?= ? ?. Fact 3: Pr[cut of size at least ??survives at time ? ] = 1 ?? ?/?? So these linear number of small cuts die out by ? = ln? + ?(1). Fact 4: At most ? 1 vertices with degrees less than ??.
gives a weaker bound Suppose only ?(?) small cuts of size in [??, 2 ? ??]. Fact 3: these small cuts die out by ? = ln? + ?(1). Fact 4: At most ? 1 vertices with degrees less than ??. Fact ?: after ? time, expected number of vertices is at most ?? ?/2. Hence, at time ? most remaining vertices have degree > 2 ? ?? So shrink from ? down to 1 at much faster rate ( ?? ? instead of ?? ?/2) This shows we stop at 1.5ln?. Hence ??(1.5 ln ?)= ? 1.5? probability of the min-cut surviving.
to go all the way To get ? ?, we need two final things (we ll skip today): 1. Differential equation tracking number of remaining vertices. 2. Concentration-of-measure to prove we stay close to this ideal trajectory.
remember, the approach Theorem: Karger-Stein outputs any fixed minimum k-cut with probability ?(? ? ?(1)). Proof outline: Define ??=??? ?. 1. refined analysis of the Karger-Stein randomized algorithm If G has only linearly many small cuts, then K-S behaves better. 2. connection of cuts in graphs to extremal results about set systems 1?? ? # small cuts with size in [??, 2 ? ??] at most ? +
the extremal bound Theorem: ? 1 ?+ ? There are at most ? ? many cuts of size at most 2 ? ??. Sanity checks: For ??: ??= 1, so zero small cuts. For ??: ?? ? 1, so ? small cuts.
proof idea 1: intersection lemmas Idea #1: ?/2 cuts of size 2 ? ?? intersecting must give < ? occupied regions, else get k-cut of value < ? ??= ???.
proof idea 2: sunflower lemmas core petals (disjoint) [Erdos and Rado]: at least ?!?? sets of size ? sunflower with ? petals Corollary: at least ? ?!?? sets of size ? sunflower w/ ? petals and nonempty core
how to use the sunflowers Assume: no cuts in the graph of size smaller than ?? Consider sets S such that boundary of size 2 ? ?? Idea #2: cannot have sunflower with non-empty core and 2/? petals If these sets S are small (with at most ? vertices) ? ? ?/?? bound. But ? could be large!
combine the two ideas = collection of small cuts of size 2 ? ??in G. Theorem: Suppose (and ) has no (2/?) sunflower with non-empty core And no ?/2 sets intersect to give ? occupied parts in Venn diagram has ? 1 ?? ? sets 1 ?? ? -- to handle cuts of size less than ?? Finally, need a little slack -- ? ? +
those were the two parts Theorem: Karger-Stein outputs any fixed minimum k-cut with probability ?(? ? ?(1)). Proof outline: Define ??=??? ?. 1. refined analysis of the Karger-Stein randomized algorithm If G has only linearly many small cuts, then K-S behaves better. 2. connection of cuts in graphs to extremal results about set systems 1?? ? # small cuts with size in [??, 2 ? ??] at most ? +
in summary Theorem: Both the combinatorial and algorithmic bounds of ??+?(1) Open questions: Get a tight bound of ? 1. ? on the number of min-k-cuts? Get 1 + ? approximation in time ? ?,? ??(1)? 2. Get a deterministic algorithm that matches this ?? bound? 3.
