Cut Sparsifiers and Graph Structures: Applications and Insights
Explore the concept of cut sparsifiers in graph structures, focusing on partitioning graph vertices, minimum-cut values, and algorithms for computing sparse weighted subgraphs. Learn about uniform and non-uniform sampling techniques, concentration arguments, and key lemmas in the field. Discover how to preserve cuts through sampling and achieve concentration in various graph structures.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Succinct Graph Structures and Their Applications Spring 2020 Class 7: Cut Sparsifiers
Cut Sparsifiers A cut is a partitioning of graph vertices into two subsets ? and ? ? The value of a cut is ??? = ? ?(?,? ?)?(?) Minimum-cut value ? = min ? ???(?) ? ?\S Goal: compute a sparse weighted subgraph ? ? such that: ? ?,??? ??(?)
Cut Sparsifiers Unweighted undirected ?-vertex graph ? = (?,?) A weighted subgraph ? ? is an (1 + ?) cut sparsifier if ? ?,??? (? ?)??(?) Today: ? ? (1 + ?) sparsifier with ? ??? ??? ? ??edges [uniform sampling, Karger 93] ? ?? edges [non-uniform sampling, Benczur-Karger 96] (1 + ?) sparsifier with ?
First Attempt Sample each edge into ? independently with probability ? All successfully sampled edges have weight ?/? ? =? ? ?[?] In expectation, all cuts are persevered! What about concentration? ? ?\S Graph with min-cut ?. Prob. of sampling no edge from a cut ? ?? ??? ?? = ???( log ?) ? = ?(????/?)
Cut Sparsifiers via Uniform Sampling Lemma 1 [Karger 93]: Let ?be an ?-vertex graph with minimum-cut ?. Let ? = ?log ?/(?2?)for some constant ?. Then, w.h.p. all cuts in ?[?]are within 1 ? their expectation. Theorem [Sparisifer]: The subgraph ? =? ? ?[?]for ? = ?log ?/(?2?) is an ? ? log ? ?2? (1 + ?) cut sparsifier with ? ?? ? ? 1 + ? ? ??(?) ? ? ? ??? 1 + ? ? 1 ? ??(?)
Lemma 1 [Karger 93]: Let ?be an ?-vertex graph with minimum-cut ?. Let ? = ?log ?/(?2?). Then, w.h.p. all cuts in ?[?]are within 1 ? their expectation. Fix one cut of value at least ? = (log?). Warm up: Prob. no edge in the cut is sampled 1 ??< ? ??= ? (log ?) Concentration argument: ?? indicator r.v for sampling ?? ? = ?? number of sampled edges. ???? ??? ? Chernoff: ?? ? ? ? ? ? ? = ???? ???? = ????( ? log?) ? W.h.p concentration holds for one cut, but there are 2? many cuts
Key Cut Lemma[Karger 93]:? 1, there are at most ??? cuts of size ? ? Fix a cut of size ? ? ???? ??? ? Chernoff: ?? ? ? ? ? ? ? = ???? ??? ? ? = ???? ? ? log? ? = ?/??(?) W.h.p. all cuts of size ?? are concentrated ? ? classes of cuts with values [??, ? + 1 ?] for every ? 1,? ? W.h.p. all cuts are concentrated
Limitations ? ? logn ??? ???(?)|) ? ? = ?(| Not useful for dense graphs with small cuts ??/2 ??/2 Approach: sample more aggressively in highly-connected regimes
Cut Sparsifiers via Non-Uniform Sampling Theorem [Benczur-Kerger 96]: For every ?-vertex graph ? and ? (0,1) there exists an (1 + ?) cut sparsifier with ?(?/?2) edges.
Towards Sparser Sparsifiers with Non-Unifrom Sampling Stronger Variant of Lemma 1 [Karger 93]: Let ?[??]where each ? ?is sampled w.p. ??. If for each cut in ? it holds that the expected #sampled edges is ?(????/??), then w.h.p. all cuts are within ? ?their expectation. Challenge: Uniform sampling: ? = ? ?[?]for ? =? ? Non-uniform sampling: ??= ?/??
The High-Level Approach Define for each edge ? a measure of importance ?? E.g., ?? measure how connected is the region to which ? belongs Sample each edge into ? with probability ??=???? ? ?? ?? Sampled edge has weight ? ??in? In expectation, all cuts are good. Concentration? Size of ? ???[??]?
Connectivity Definitions A subgraph ? ? is ?-connected if ???- -??? ? ? A ?-strong component of G is a maximal ?-conn. vertex-induced subgraph of ? The strong connectivity of an edge ? denoted by ??is the max value ?such that there is a k-strong component containing ? The standard connectivity notion of ? = (?,?)denoted by ?? is the value of the minimum ?-? cut (# ?-? edge-disjoint paths) ??/2 ??/2
Examples ? ? ? ?1 ?2 ??= n 1 ??= 2 ?3 ???= ?
Observations ? ? ? Obs. 1: ?? ?? Proof: Maximal vertex-induced subgraph ? = ?[?] such that ? ? and ? is ?? connected. ??= ???-??? ?,?,? ???-??? ?,?,? ?? Obs. 2: If? belongs to cut in ? of size ? then ?? ? Proof: ?? ?? ? Obs. 3: If ?belongs to the min-cut then ??= ??
Key Property of Strong Connectivity Def: An edge ?is ?-strong if ?? ?, otherwise it is ?-weak Lemma 2 [Benczur-Karger 96]: Deleting ?-weak edges does not change the strength of any of ?-strong edges Proof: ?belongs to a ?-strong conn. component ? ? ,then all edges in ?[?] are ?-strong. Note: This property does not hold with the standard connectivity definition
? ? ? ?
Improved Cut Sparsifier ? ??, where ? =? ??? ? Algorithm: Sample each edge ?with probability ??= Every sampled edge ? has weight ?/?? in H. . ?? ? ?? edges. Lemma [Size]: W.h.p. ? has ? 1 ?? ? 1 Show that ? Lemma [Concentration]: W.h.p. for every ? ?,??? ? + ? ??(?) Show that exp. number of sampled edges in each cut is (log?/?2)
1 ?? ? 1 Lemma: Lemma: ? Partition edges into ? 1edges sets ??, ,?? ?such that ? ???/?? ? ?1 edges of the min-cut in ?. ? ?? ? For every ? ??: ??= ??= ?? ? |??| ? Remove ?1 from ? and continue on each comp. of ? ?? Every component of ? ?? is vertex-induced subgraph. Comp. ? with minimum-cut edges ?? of size ? . ? is ? -strong-connected component and thus ?? ? for every ? ? ? ???/?? ?
1 ?? ? 1 Lemma: Lemma: ? Partition edges into ? ?edges sets ??, ,?? ?such that ? ???/?? ? In each step ? given a ? strong connected component ?? Define ??to be min-cut edges in ??: ?? ? for every ? ??and thus ? ???/?? ? ?? ??has two components that are vertex-induced subgraphs Each step increases number of components by one At most ? 1 steps
Cut Analysis: Every Sampled Cut is Large in Exp. ??=:? ?,?,? where ? ? = 1/?? and ??= ?/?? ? = ??[??] View ?? as summation of uniformly weighted graphs ?1< ?2< < ?? strong connectivity values Subgraphs ?? {? ? ?? ??} ?? ?? ? ? ??= ?? ? ?-length vector of edge weights
An edge ? with ??= ?? appears in ??,,?? ? ? =?1 ?+?2 ?1 + +?? ?? 1 =?? ? ?? ?= ? ? To generate ??[??]each edge ? is sampled w.p. ?? and if sampled ? ??,??, ,?? where ??= ?? Sampling in ??translates into sampling in ?? The subgraphs ?1, ?? are dependent but sampling to ?? is independent
Cut Concentration in ?? Sufficient to show ? ???= ?(????/??) for every cut edges ? ?? 1. ???? = ??(?) Why: removing ??-weak edges does not change strong-connectivity 2. ???? ?(definition of edge connectivity) ? 3. ???? ??(??) ??? = ???? ???? |?| ? ?? ???? ?? ? ??= ? = ? ? ? ? ?
So-far: all cuts of ?? are concentrated w.h.p. Goal: ??? ? ? ??(?) ? ? ? ?1 ?1 ?2 1 ? ? ? ?1?? 1. ? ?1?? 1 ? ? ? ?2?? 2. ? ?2?? ?2 ?1 3. ? = ???? =?1 ??1?? +?2 ?1 ?2?? ? ?1 ? ? ? ?1 ??+?2 ?1 ? = ?(?,? ?) ??? 1 ? ?? ? ? ? ?2
? ? ? ?1 ? ? ? ?1 ??+?2 ?1 ??? 1 ? ?? ? ? ? ?2 ?1 ?1 ?2 ?1 ? ?? +?2 ?1 1 ? ??+ ?? ? ? ?1 ? ?2 ? ?2 ?2 ?1 ?1 ? ??+?2 1 ? ? ?? ? ?1 ? ?2 1 ? |?1| + |?2| ? = ?(?,? ?) ?1= {? ? ??= ?1} ?2= {? ? ??= ?2}
