Labeling Schemes for Succinct Graph Structures and Applications
Explore informative labeling schemes for graphs, including adjacency, distance, and flow labels, in the context of representing graphs efficiently. Understand the complexities and design of labeling functions for various graph structures and universal graph families. Dive into adjacency labeling schemes for trees and the importance of concise labeling in graph theory applications.
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 5: Labeling Schemes
How to Represent a Graph? Conventional approach: node-IDs e.g. ?(log?)-bit identifiers Today: meaningful identifiers Problem 1: Label the vertices of an ?-vertex tree ? with ?(log ?)bits, such that given ?(?) and ?(?) can determine if ?,? ?? Problem 2: Build an ?(?2)-vertex graph that contains all ?-vertex trees as vertex-induced subgraphs*. * A subgraph ? = (? ,? ) ? is vertex-induced subgraph if ? = ? ? ?(?)
Informative Labeling Schemes Function ?:?? ? defined on subsets of ? vertices ? = {??, ,??} ?. ?-labeling scheme assigns labels ?(?) to all vertices such that ? ? can be computed given ? ??, ,? ??. In this class: ? = ?. Examples: adjacency labels, distance labels, flow labels, etc. ? ?,? = ???,? ? ?,? = ??????,? ? ?,? = 1 iff ?,? ? Complexity measure: label size
Informative Labeling Schemes An ?-labeling scheme ??,?? consists of: Encoding function ??: ? {?,?} assigns distinct -bit labels ??? ,? ? Decoding function ??: ?,?? ?such that ?? ??? ,??? = ?(?,?) Note: the labeling function ?? gets to see that graph, but the decoding function ?? sees only the labels (and the graph family if relevant)
Outline Adjacency labeling schemes Trees Universal graph families Distance labels for general graphs Flow and connectivity labels Distance labels for bounded-separator graphs
Adjacency Labeling Schemes ? ?,? = 1 iff ?,? ? ? No! Question: Is it possible to have labels with ?(log n) bits? The labels ? ??, ,? ??fully encode ? The total number of ?-vertex graphs is 2?2 thus require labels of ?(?)bits ? log? -bit schemes for sparse graphs (e.g., trees, planar graphs) ?(log?)-bit scheme for family ? ? = 2?(?log ?)
Adjacency Labeling Schemes for Trees ? 2log?-bit scheme: ? ? = ?? ? ,??(?(?) ? Cor.: planar graphs have ?(????)-bit scheme ? ? ? [Alstrup, FOCS 15]: ???? + ? ? bits ? ? ? ? ? Why should we care so much about these constants?
Induced Universal Graphs A graph U=(?,?) is an induced universal graph for a graph-family if ? there is an induced subgraph of U that is isomorphic to ?. Theorem: A family of graphs has -bit adjacency labeling scheme iff it has an induced universal graph with 2 vertices
Theorem [KNR 88]: A family of graphs has -bit adjacency labeling scheme iff it has an induced universal graph with 2 vertices Universal graph ? = V,E where: ? = {0,1} -bit scheme ?,? to universal graph ? ?,? ? ? iff ?(? ? ,? ? ) Assign IDs in ?,? to ? ? Universal graph ? to -bit scheme Given ?, find ? ? ? such that ? ?[? ] Assign labels to ? ? based on mapping to ?
(Exact) Distance Labeling for Trees Recup: heavy-light tree decomposition Heavy child is the child of largest subtree Key property: any path from root to node ? contains ?(log?) light edges Theorem: There is an ?(?????)-bit distance labeling scheme for trees.
Theorem: There is an ?(?????)-bit distance labeling scheme for trees. ? ??? is a sketch of the path ? ?,? : Partition ?(?,?) into segments of heavy-edges interleaved with light-edges. ? ?,? = ?? ?? ?? ?? ?? ? ? Replace every heavy-segment ?? by its length ??? = ??,??, ??,??,??, ,|? | Label size is ?(log2?) bits
??? = ??,??, ??,??,??,,|?| ??? = ?? ,? ?, ?? ,? ?,? ?, ,|? | Decoding Find the first point of difference in the labels ? Deduce the length of mutual segment ? |? ?,? ?(?,?)|(depth of ??? ?,? ) Deduce the length of the remaining segments
SepLevl Labels Separation level of trees: ???????? ?,? = Depth(LCA u,v ) ???(?,?) Cor.: There exists an ?(log2?)-bit SepLevel labeling schemes for trees. ? ?
Approximate Labeling Scheme for Weighted Graphs ?-approximate labeling scheme ?,? :? ? ? ,? ? [ ???,? ,? ???,? ] Immediate By Thorup-Zwick oracles: Bunch ?(?)with ?(??/?)vertices and ? pivots ??? , ,?? ?(?) (?? ?) approximate distance labels: ? ? = ? ? ,??? , ,?? ?? ,{???,? ? ? ? } Label size: ?(??/?)bits For stretch < ?: ?(?)bits [GPPR01]
Bunches A0= A1= A2= p2(v) v p1(v) ??? { ? ?? ??+1 ? ?,? < ?(?,??+1? )} *Slide taken from Uri Zwick presentation 15
Approximate Labeling Scheme for Weighted Graphs ? ? = ? ? ,??? , ,?? ?? ,{???,? ? ? ? } Decoding ?(?) and ? ? : ??(?) 1. Find min ? such that either ??? ?(?)or ??? ?(?) 2. Return ???,??? + ??(??? ,?) ? ?
Labeling Scheme for Flow and Connectivity Graph ? = (?,?,?)where ?:? ?capacity (edge multiplicity) ???? ?,? maximum number of edge-disjoint ?-? paths 1 1 Theorem: Every ?-vertex graph ? = (?,?,?)has an ?(????(?? ))-bit labeling scheme for flow where ? is the largest edge capacity. 2 5 1 4 3 1 5 5 Tool: Sep-Level labeling scheme for trees with ?(?????) bits 5 6 Depth of ???(?,?)
Labeling Scheme for Flow and Connectivity ``? and ? admit a flow at least ? is an equivalence relation Lemma: The relation ??= { ?,? ?,? ?, ???? ?,? ?}is an equivalence relation. E.g., ?,? , ?,? ??then ?,? ?? ??} s.t: ?,?? ?, ,?? ?? defines a collection of equivalence classes on V: ?= {?? ?= and ??? ? ?? ?= ? ??
Labeling Scheme for Flow and Connectivity ??} ?,?? ?, ,?? ?? defines a collection of equivalence classes on V: ?= {?? Observation: ?is a refinement of ? ? 1 1 ?= ? 1 1,2, ,6 2 5 1 ?= ? , ?,?,?,?,? 2 4 3 2, ,6 1 1 5 5 3 1 2,3 ?= ? , ?,? ,{?,?,?} 4,5,6 5 6
Labeling Scheme for Flow and Connectivity Compute a tree ?? of ? representing the flow-relations and containments ??} ?,?? ?, ,?? Nodes of level-? correspond to components of ?= {?? Each leaf node correspond to a vertex in ? Number of vertices in ?? is ?(?2 ? )
Level 1 ??????,? = ?????????? ? , ? + ? 1,2, ,6 2 2, ,6 1 Leaf node in ?? that corresponds to ? 1 1 2,3 4,5,6 3 2 5 1 4 2,3 4,5,6 4 3 Since ?? = ?(? ? ), 1 5 5 5 2,3 4,5,6 label size =?(log2 (? ? )) 5 6 6 4,5 6 2,3 7 5 4 6 3 2
Distance Labeling and Separators Graph Separator: Set of vertices ? whose removal disconnect the graph Balanced Separator: Separator ? whose removal leaves components of size 2? 3 A family of graphs has ?(?)-separator if every ?-vertex graph ? has a separator of size ?(?) Here: graph families that are closed under subgraph Examples: planar graphs ? ? = ? forests ? ? = ? bounded tree-width ? ? = ?(?) ? ?
Distance Labeling and Separators Theorem [GPPR01]: Every family with ? ? -separator has (exact) distance labeling scheme with ? = ?(? ? log ?+log2?) bits where ????/?? ?(? ?/??) ? ? = ?=? Open problem for planar graphs: ? = ?(??/?) Examples: planar graphs ? ? = ? forests ? ? = ? bounded tree-width ? ? = ?(?) ? ? = ?( ?) ? = ?(log??) ? = ?(log??)
Distance-Labeling Scheme for ?(?)-Separator Family 1. Compute a separator ? ?of size ?(?) 2. Let ??, ,? be connected components of ? ? ?1 3. For each ??recursively compute labels for ?(??) ?2 4. Label of each ? ?? has three fields: ? Distances to each ? ? 1. ID of component ?? 2. Label ?(?,? ??) computed in Step 3 3. 5. Label of each ? ?contains fields 1,2
Distance-Labeling Scheme for ?(?)-Separator Family Case 1: the ?-? shortest path goes through ? ? ? ?1 ?2 ?(?) contains ???,? ? ? contains ??(?,?) ? ?,? = ??? ? ????,? + ??(?,?)
Distance-Labeling Scheme for ?(?)-Separator Family Case 2: the ?-? shortest path does not go through ? ? ? ?1 ?2 Follows inductively by the correctness of ?(?,? ?1) and ?(?,? ?1) Claim [Label Size]: 2? 3 ? + O(r n logn)
