Gomory-Hu Trees and Min-Cut Representations in Graph Structures
Explore Gomory-Hu trees and efficient min-cut representations for graph structures, highlighting the significance of minimum cuts and their applications. Understand the Triangle Inequality Lemmas, submodularity, and the importance of tree-based computations in 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. 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 9: Gomory-Hu Trees
Min-Cut Representation A cut is a partitioning of graph vertices into two subsets ? and ? ? The value of a cut is ??? = ? ?(?,? ?)?(?) ? Minimum-cut value ? = min ? ???(?) Minimum ?-? cut ??(?,?)= ? ?,? ?,? ???(?) min ?\S Goal: Succinct representation of all minimum cuts Efficient computation of all minimum cuts
Gomory-Hu Tree Given is a graph ? = (?,?,?). A Gomory-Hu tree is a weighted tree ? = (?,? ,?)such that ? ? = ? ? ???,? = ???{?(?) ? ??(?,?)} Special Bonus: computed by applying ? 1 min-cut computations
Example ? 8 3 ? ? ? 1 6 6 7 2 ? ? 1 1 ? ? 6 2 7 ? ? ? 4 8 ?
Min-Cut Follows the Triangle Inequality Lemma 1: ???,? min ???,? ,??(?,?) for every ?,?,? ? ? Case 1: ? ? ???,? ??(?,?) Case 2: ? ? ???,? ??(?,?) ? ? ? = ?\A
Min-Cut Follows the Triangle Inequality Lemma 2: for every sequence [?,?1,?2, ,??,?] it holds that ???,? ??? ???,??,????,??, ,??(??,?) ? ? Proof: repetitive applications of Lemma 1. ? ? ? = ?\A
Tree with ?(?2) Min-Cut Computations Let ? = (?,? ,?) be a ? ? ?(?) clique where ? ?,? = ??(?,?) Compute a maximum spanning tree ? ? Lemma 3: for every ?,?it holds that ???,? = ??? {? ? ? ???,? } Proof: Trivial for ?,? ?.Assume otherwise. By the triangle inequality: ???,? ???{? ?,??,? ?,??, ,?(??,?)} Since ?,? ? ?:???,? ???{? ?,??,? ?,??, ,?(??,?)} As ? is a max spanning tree
Tree with ?(?2) Min-Cut Computations Let ? = (?,? ,?) be a ? ? ?(?) clique where ? ?,? = ??(?,?) Compute a maximum spanning tree ? ? Lemma 3: for every ?,?it holds that ???,? = ??? {? ? ? ???,? } Main Drawback: requires (?2) min-cut computations.
Nice Properties of Cuts Submodularity: Given a finite set ? , a function ?:?? is submodular if for all ?,? ?? it holds that ? ? + ? ? ? ? ? + ?(? ?) Equivalent Definition (Decreasing marginal value): ?is sub-modular if ? ? + ? ? ? ? ? + ? ?(?)for all ? ?and ? ?. Symmetric Submodular: ? ? = ?(? ?)for all ? ?
Nice Properties of Cuts ? In our case graph ?(?,?) and ?:?? where ? ? = ?(?) ? ? Lemma: The cut function is submodular Diagram with all classes of edges (except fully inside ?,?,? (? ?)) ? ? ? ? ? + ? ? = ? + ? + 2? + ? + ? + 2? ? ? ? ? ? = ? + ? + ? ? ? ? ? ? = ? + ? + ? ? ? ? + ? ? ? = ? + ? + 2? + ? + ? ? ? + ?(?) ?
Nice Properties of Cuts A function ?:?? is posi-modular if ? ? + ? ? ? ? ? + ?(? ?) Obs.: Any submodular and symmetric function is posi-modular ? ? + ? ? = ? ? ? + ? ? ? ? ? ? + ? ? ? ? =? ? ? + ? ? ? ? = ? ? ? + ?(? ?) The cut function ? ? = ?(?) is posi-modular
The Key Lemma Key Lemma: Let ?(?)be an ?,? minimum-cut in a graph ?. For every ?,? ? there is a min ?,? cut ?(?) in ? where ? ?. ? ? This implies that the min ? ?cut in a graph ? obtained by contracting all nodes in ? ? is the same as the ? ? cut in ? ? ? ? ? ? ? ? ? ? ? ?
Key Lemma: Let ?(?)be an ?,? minimum-cut in a graph ?. For every ?,? ? there is a min ?,? cut ?(?) in ? where ? ?. Let ?(?) be any ?,? min cut that crosses ?. W.l.o.g. assume that ? ?,? ? and ? ? Case 1: ? ?. ? ? + ? ? ? ? ? + ?(? ?) ? ? submodularity ?(? ?) is ? ? cut ?(? ?) is ? ? cut ? ? ? ?(?) ? ? ? ?(?) ? ? ? ? ? + ? ? ? ? ? + ?(? ?) ? ? ? = ? ? ?
Key Lemma: Let ?(?)be an ?,? minimum-cut in a graph ?. For every ?,? ? there is a min ?,? cut ?(?) in ? where ? ?. Let ?(?) be any ?,? min cut that crosses ?. W.l.o.g. assume that ? ?,? ? and ? ? Case 2: ? ?. ? ? + ? ? ? ? ? + ?(? ?) ? Posi-modularity ? ?(? ?) is ? ? cut ?(? ?) is ? ? cut ? ? ? ?(?) ? ? ? ?(?) ? ? ? ? ? + ? ? ? ? ? + ?(? ?) ? ? ? = ? ? ?
High-Level Intuition Compute an ? ? minimum cut for an arbitrary pair ?,? ? ? ? ? By the key lemma: For every x,y ?, ? ? internal in ? For every x,y ?, ? ? internal in ?
High-Level Intuition Compute a ? ? minimum cut for arbitrary pair ?,? ? ??(?,?) ? Break the task into two independent computations! ? ? Compute tree ?? for ?? ?? ? ?? ? Compute tree ?? for ?? ?? ??
High-Level Intuition Collapsing a set ? into a vertex ??: For each ? ? add edge (?,??) of weight ? ?,?? = |{ ?,? ? ? ?}| ? ?? ??
High-Level Intuition Compute a ? ? minimum cut for an arbitrary pair ?,? ? ??(?,?) ? Break the task into two independent computations! ? ? ? ??(?,?) ?? Compute tree ?? for ?? ?? Compute tree ?? for ?? ?
Gomory-Hu Algorithm ?(?) = {??} and ? ? = Repeat until all vertices in ? are singletons: Pick a non-singleton ?? ?? 1. Define ? by collapsing each vertex ?? ?? {??} 2. Compute ? ? min-cut ?,? in ? for arbitrarily chosen pair ?,? ? 3. ?? (?,?) ? ?2 ? ?1 ? ? ? ? ? ? ?
Gomory-Hu Algorithm ?(?) = {?} and ? ? = Repeat until all vertices in ? are singletons: Pick a non-singleton v? ?? Define ? by collapsing each vertex ?? ?? ?? Compute ? ? min-cut ?,? in ? for arbitrarily chosen pair ?,? ? 1. 2. 3. Split ? into ??= ? ?and ??= ? ? and add ? ???,???= ?? (?,?) 4. For every earlier edge ??,?? do: 5. If ? ?, replace it with ??,??1(same weight as ??,??) 1. Otherwise, replace with ??,??2 (same weight as ??,??) 2.
Illustration 3 ? ? 1 6 ?,?,?, ?,?,? 2 1 1 ? ? 2 7 ? ? 4 1. Pick ?,? ? 6 ?,? ?,?,?,?
2. Pick ?,? ? 3 ? ? ? 4 6 1 6 2 1 1 ?? ? ? ? 2 2 7 ? ? 4 8 6 ?,?,?,? ? ?
2. Pick ?,? ? 3 3 ? ? ? ? 1 6 1 6 2 2 1 1 ? 1 1 ? ? 2 2 7 ? ? 7 ? ? 4 4 8 6 8 ? ?,?,? ? ?
2. Pick ?,? ? 3 ? 3 ? ? ? 6 1 1 6 2 1 2 1 ? ? 1 1 ? ? 2 2 ? 7 ? 7 ? ? 4 4 8 6 8 ?,? ? ? ? 7 ?
2. Pick ?,? ? 3 3 ? ? ? ? 6 1 1 6 2 2 1 1 1 1 ? ? ? 2 2 7 ? ? 7 ? ? 4 4 6 6 8 8 ? ? ? ? ? 7 ?
Correctness Analysis Claim: ?? (?,?)=??(?,?) ?? (?,?) ?2 ? ?1 ? ? ? ?
Correctness Analysis Lemma: ???,? = min{ ? ? ? ???,? } Observation: ???,? min{ ? ? ? ???,? } This holds as every edge in ???,? corresponds to a ? ?cut in ? Can be shown by induction on the length of the path.
Correctness Analysis Lemma: ???,? = min{ ? ? ? ???,? } ? Observation: ???,? min{ ? ? ? ???,? } ?2 Claim: ???,? min{ ? ? ? ???,? } ?1 ?? Key Claim: For every edge ?,? ?,???,? = ?(?,?) ? ? Triangle ineq. ???,? min ? ?,?1,? ?1,?2, ,? ??,? = min ? ?,?1,? ?1,?2, ,? ??,?
Correctness Analysis Key Claim: For every edge ?,? ?,???,? = ?(?,?) Step ? {?, ,? ?}: Weighted tree ?? Each node ?? ? ?? corresponds to a subset ? of vertices in ?(?) Claim: For every edge ??,?? ?? there exists ? ?,? ?such that ? ??,?? = ??(?,?) Shown by induction on ?
Correctness Analysis Claim: For every edge ??,?? ?? there exists ? ?,? ?such that ? ??,?? = ??(?,?) Base of induction: ?1 has no edges, trivial Induction step ?:Split a super-vertex ?? ?? ?into ?1,?2 ?? (?1,?2) ?? ? ?? ?2 ?? ?? ?? 1 ?1 ?? ? ? ? ?
Correctness Analysis Claim: For every edge ?,? ?? there exists ? ?,? ?such that ? ?,? = ??(?,?) Base of induction: ?1 has no edges, trivial Induction step ?:Split a super-vertex ? ?? ?into ?1,?2 ??(?1,?2) ?? ? ?? ?2 ?? ?? ?? 1 ?1 ?? ? ? ? ? Show that claim is preserved for ?1,? !
Correctness Analysis Induction step ?:Split a super-vertex ? ?? ?into ?1,?2 ??(?1,?2) ?? ?2 ?? ?? ?? 1 ? ? ? ?1 ?? ?(?,?) ?? ? ? ? ? ? ? By induction assumption for ? ?: ? ? and ? ? such that ? ?,? = ?(?,?) If ? ?1 Otherwise, show ? ?? such that: ? ?,? = ???,? = ??? ,? = ?(??,?)
??(?1,?2) ?? By the triangle inequality: ?2 ?? ? ?1 ? ?,?? ???{? ?,? ,? ?,??,?(??,??)} ?? ?? ? By the key lemma: collapsing ?2 does not change value of ?(?,?1) ? ?,?? ???{? ?,? ,?(??,??)} The?? ?? min cut also separates ? and ?, thus ? ?,? ?(??,??) ???,?? ???,? As there is an ? ?? cut of value ???,? ???,?? = ???,?
Implications For any undirected graph there is a pair of nodes ?,? such that there is an ? ?min cut that consists of a singleton node (a.k.a pendant pair). Let G be a graph such that deg(?) ? for all ? ? then there is a pair such that ???,? ? Submodularity and symmetry are sufficient conditions for tree representation with ? 1 computations.
