Efficient Cut Algorithms in Graph Structures

This content covers efficient cut algorithms in graph structures, focusing on partitioning graph vertices, computing minimum-cut values, and a short history of min-cut algorithms. It explains the contraction algorithm, cut sparsifier subgraph computation, and the general contraction algorithm. The material also delves into key cut lemmas and the last week's discussion on linear time computations and cut sparsifiers, along with their applications.

• Graph Structures
• Cut Algorithms
• Minimum-Cut
• Contraction Algorithm
• Efficient Algorithms

mit_wie Follow

Uploaded on Feb 17, 2025 | 0 Views

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.

Presentation Transcript

1. Succinct Graph Structures and Their Applications Spring 2020 Class 8: Efficient Cut Algorithms

2. Efficient Cut Algorithms Cut Counting Argument (debt from last week) Towards linear time algorithm: Tree Packing Next Week: Gomory Hu

3. Cut A cut is a partitioning of graph vertices into two subsets ? and ? ? The value of a cut is ??? = ? ?(?,? ?)?(?) ? Minimum-cut value ? = min ? ???(?) ?\S

4. Short History of Min-Cut Algorithms [FF62]: ?2 computations of min ? ? cuts in ?(??2) [GH61, HO04]: ? 1 computation of min ? ? cuts in ?(??) [Gabow, 95]: ?(??) for graphs with min cut ? [KS, 96]: random contraction algorithm in ? ?2 [Karger, 97]: (1 + ?) approximation in ? ? [Karger, 98]: Exact computation in ? ?

5. Last Week Key Cut Lemma[Karger 93]: ? 1, there are at most ??? cuts of size ? ? Tight for cycles Theorem [Karger 93] : In linear time, one can compute a (1 + ?) cut sparsifier subgraph ? ? with ?(? log ? ??2) edges and unweighted min-cut c = ?(log?/?2) . The min-cut in ? corresponds to a cut in ? of value at most 1 + ? c (1 + ?) approximate cut in ? ? time

6. The Contraction Algorithm [Karger and Stein 96] ?1 ?2 Contraction operation ??,??: Replace by a single vertex ? and a union of ?? and ?? edges ? ? ? Might form multiple edges (no self-loops) Contract ?1,?2 ? ??,?? graph ? with edge (??,??)contracted ? ? graph ? with edges ? contracted ? Every contraction operation reduces number vertices by one ? ? ?

7. The Contraction Algorithm [Karger and Stein 96] General Contraction algorithm: Repeatedly contract edges until two super-vertices remain (define a cut) ? ? ?set of vertices of the super-vertex ? ? contract (?,?)to a vertex ? with ? ? = ? ? ?(?) ? ? ? ? Every cut in contracted graph corresponds to a cut in ? ? ? ?

9. The Contraction Algorithm [Karger and Stein 96] General Contraction algorithm: Repeatedly contract edges until two super-vertices remain (define a cut) Lemma: A cut (?,? ?)is output by a contraction algorithm iff no edge crossing (?,? ?)is contracted by the algorithm. If edge ?,? ?(?,? ?)is contracted, ?,?are in the same super-vertex. If ? ?and ? ? ?are in the same super-vertex Exists a ? ?path contracted by the algorithm Exists an edges in ?(?,? ?) contracted by the algorithm

10. The Contraction Algorithm [Karger and Stein 96] Algorithm ????????(?): Repeat until ? has two vertices: choose an edge (?,?) uniformly at random from ? set ? ? (?,?) 1 ? 2 Lemma: A particular minimum cut is returned by the algorithm w.p

11. 1 ? 2 Lemma: A particular minimum cut is returned by the algorithm w.p Min-cut (?,? ?)with ? = |? ?,? ? | (?,? ?)is output iff no edge in ? ?,? ? is contracted Observation: min-cut in contracted graph ? is at least ?. Why? Consider step where number of vertices in ? is ? ? ? Claim: ? ? ? Probability of choosing a cut-edge to contract ?/?

12. Prob. of never contracting any cut edge in ? ?,? ? : ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ?(? ?) ?(??????) time algorithm for computing minimum-cut

13. Cut Counting Through Contraction Corollary: The number of minimum cuts is t most ? ? ? The probability to output a fixed minimum cut is ? ? Since exactly one cut survives, the survival events of distinct min cuts are disjoint ? =: number of minimum cuts ? ? ? ? ? ? ? ?

14. ?-Approximate Cut Counting Lemma: For ?a half-integer, the probability that a particular ?- ? ? ?? minimum cut survives contraction to 2? vertices is (?,? ?):= cut of size at most ? ? Step where G has ? vertices and min-cut at least ? ? ?/?=?? ?? Probability of contracting a cut-edge is at most ? Probability that the cut survives: ? 1 2? 2? ? 1 2? ? ?? 1 1 = ? 2? + 1

15. Lemma: For ?a half-integer, the number of ? minimum cuts is at most ??? . Once reaching ??vertices possibly more than one cut survives Take a random partition of ??vertices unique cut A fixed cut is output with probability ? ? ?? ? (?? ?) ? ?? 22? 1 2? ! Over-all, number of ?-approx. cut is ???

16. Near Linear Time Algorithm (Karger, 98) Based on duality between minimum cuts and tree packing Find efficiently a spanning tree ? that has at most two edges in common with a minimum cut Apply dynamic algorithm to find the two-cut edges in ? Starting point: Every tree intersects every cut (at least one mutual edge) Potentially, a tree might contain all edges of minimum cut

17. Cuts and Tree Packing Definition: Let ?be a spanning tree of ?. A cut in ??-respects ? if it cuts at most ? edges of ?. Theorem: Given a tree ? such that the minimum cut 2-respects it, one can compute the minimum cut (in G) in ?(? ?????)time Goal: Find (efficiently) a tree?such that the minimum-cut 2-respects ?. Linear time

18. Trees and Cuts

19. Tree Packing For unweighted graph: A collection of edge disjoint trees Weighted Packing: A collection of (weighted) trees ??, ,? satisfying that for every ??:? ????? ?(??) for every edge e. The value of the packing is ??? Lemma (Nash-Williams, 61): Any undirected graph with min-cut ? contains a tree packing of at least ?/? trees Exists a tree ? in the packing such that the minimum cut 2-respects it

20. A tree is good if min-cut two-respectsit So-far: 1 among ?/2 trees is good Next: half of the ?/2 trees is good Next next: 1/3 of ?(log ?) trees is good

21. Cuts and Tree Packing Lemma 1: Given any (weighted) tree packing of value ??, and any cut of value ??, then at least a (? ? ?)/? fraction of the trees (by weight) ? respect an cut. Proof: Each tree ? in the packing has weight ?? thus ??= ? ?. Pick a tree ? at random w.p. ??/?? ?? # edges crossing ? ? cut -1 (Note:?? 0) ????+ 1 ?? (Tree packing) ???? ?? ??= ?? ?? ? ?? = ???? ? ? 1 ??

22. ? ?? =???? ? ? 1 ?? ? ? 1 2 = 1/2 3 ? By Markov: Pr ??< 2 1 ? As ?? is integer, Pr ?? 1 1/2 3 ? ? ? minimum cut 2-respects ? Corollary: In any maximum packing, the minimum cut 2-respects at least half of the trees ? =? ? and ? = ?

23. Cuts and Tree Packing Computing ?/2 packing of ?-connected graph in ?(??) time Minimum cut algorithm in ?(??) time Sample ?(log? ) trees in the packing Find the minimum cut that 2 respects the tree in ?(?) time Improvement via (? + ?) cut sparsifier Theorem [Karger 93] : In linear time, one can compute a (1 + ?) cut sparsifier subgraph ? ? with ?(? log ? ??2) edges and unweighted min-cut c = ?(log?/?2) . The min-cut in ? corresponds to a cut in ? of value at most 1 + ? c

24. Cuts and Tree Packing via Sampling Lemma: Given any (possibly weighted) graph ? in ?(?)time can compute a set of ?(????) trees s.t the G-minimum-cut 2-respects 1/3 of them w.h.p Compute a (1 + ?) sparsifier ?in linear time (``skeleton graph ) Compute a tree packing ? of ? /? trees in ? where ? = ?(????/??) in ? ? time Claim: For a Minimum cut (?,? ?) in ?, ??? ? + ? ? Set ? = (1 + ?) and ? = 1/2 in Lemma 1, and ? =1 6 1 2 ? =1 min-cut E(?,? ?) 2-respects 3 of the trees in ?