Adjacency Labeling Schemes and Induced-Universal Graphs
Adjacency labeling schemes involve assigning L-bit labels to vertices in a graph for efficient edge determination. The concept of induced-universal graphs is explored, where a graph is universal for a family F if all graphs in F are subgraphs of it. Theorems and lower bounds related to adjacency labeling schemes and induced-universal graphs are discussed, along with proofs and implications for 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
Adjacency labeling schemes and induced-universal graphs How to save lgn bits Stephen Alstrup Univ. of Copenhagen Haim Kaplan Tel Aviv Univ. Mikkel Thorup Univ. of Copenhagen Uri Zwick Tel Aviv Univ. June 1, 2014
Adjacency labeling schemes An L-bit adjacency labeling scheme for a family F of n-vertex graphs is a pair of functions: Label: receives a graph G from F and assigns each of its vertices an L-bit label Edge: receives two L-bit labels and decides whether the corresponding vertices are adjacent Note that Edge only sees labels. It does not know the graph G, nor the identity of the vertices
Adjacency labeling schemes Family Lower bound n n/2 n/4 Upper bound n + lgn n/2 + lgn n/4 + 2lgn Reference Directed graphs Undirected graphs Bipartite graphs folklore Moon (1966) Lozin-Rudolf (2007) Max deg d (even) Max deg d (odd) (d/2) lg n (d/2) lg n (d/2) lg n + O(1) (d/2) lg n + O(1) Butler (2009) Alon-Capalbo (????) Planar graphs Trees Trees of depth d lgn lgn lgn 2lgn + O(lglgn) lgn + O(lg*n) lgn + 3lgd + O(1) Gavoille-Labourel (2007) Alstrup-Rauhe (2002) Fraigniaud-Korman (2010) We improve the first three upper bounds to n+O(1), n/2+O(1) and n/4+O(1), respectively
Induced-universal graphs A graph G is an induced-universal graph for a family F iff every graph from F is an induced-subgraph of G Theorem: [Kannan-Naor-Rudich (1992)] F has an L-bit adjacency labeling scheme iff it has an induced-universal graph on at most 2L vertices Proof: Easy! Each possible L-bit label is a vertex of the universal graph Edge determines the edges in the induced-universal graph
Trivial lower bound Theorem: [Moon (1966)] Any adjacency labeling scheme for a family F of (named) n-vertex graphs must have L > (lg|F|)/n (Named (labeled) graphs are graphs on V={1,2, ,n}) Proof: Again easy! The labels assigned to all vertices determine the graph Number of possible label assignments to vertices is 2nL Hence |F| 2nL Exercise: Prove a strict inequality
Trivial lower bound Theorem: [Moon (1966)] Any adjacency labeling scheme for a family F of (named) n-vertex graphs must have L > (lg|F|)/n There are 2n(n 1)directed graphs on n vertices L n There are 2n(n 1)/2undirected graphs on n vertices L n/2 Essentially all lower bounds follow from this theorem
Induced-universal graphs for undirected graphs Size O(n2n/2) O(n22n/2) O(2n/2) Reference Moon (1966) Bollob s-Thomasen (1981) here
Trivial upper bound for directed graphs An n-vertex directed graph corresponds to an n by n Boolean matrix (known as its adjacency matrix) Let the tag of a vertex be its row in the adjacency matrix Given the tags of two vertices, we can determine whether there is an edge from the first to the second Not really! Tags are not enough, we also need the indices of the vertices. label = ( index , tag ) The trivial upper bound is thus, L = n + lgn 1 We improve this to L = n + O(1)
Upper bound for undirected graphs [Moon (1965)] Arrange the n vertices of the undirected graph in a cycle The tag of a vertex is its adjacencies to the n/2 vertices following it on the cycle
Upper bound for undirected graphs [Moon (1965)] 0 1 tag(0) = 101011 11 2 10 3 9 4 8 5 7 6
Upper bound for undirected graphs [Moon (1965)] 0 1 tag(0) = 101011 11 2 tag(1) = 001101 10 3 9 4 8 5 7 6
Upper bound for undirected graphs [Moon (1965)] Arrange the n vertices of the undirected graph in a circle Let the tag of a vertex is its adjacencies to the n/2 vertices following it on the cycle Given the tags and indices of two vertices, we can determine whether they are adjacent label = ( index , tag ) Moon s upper bound is thus, L = n/2 + lgn We improve this to L = n/2 + 4
Trick 1: Run length encoding Representing unbalanced bipartite graphs n k < lgn Main idea: Reorder the columns so that rows, and especially the first ones, are composed of a small number of runs Note: The n vertices are still given indices, but we use the freedom to choose these indices
Sort the columns! n 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 k < lgn The i-th row composed of at most 2iruns Number of bits needed to represent the i-th row is
Slightly better: Use Gray code! n 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 k < lgn The i-th row now composed of at most 2i 1+1 runs Number of bits needed to represent the i-th row is Saves a bit
n/2+(lgn)/2+O(1) for undirected graphs k = lg n c n k A B Use Trick 1 to represent A B This assigns indices to vertices of B Use Moon to represent edges within A and within B First improvement over Moon. Still some slack
Trick 2: Spreading Unbalanced representation of bipartite graphs B A We can split the bits of A B in any fixed manner, not depending on the graph itself
Trick 2: Spreading Unbalanced representation of bipartite graphs B A We can let the vertices of A have all the bits
Trick 2: Spreading Unbalanced representation of bipartite graphs B A We can let the vertices of B have all the bits
Trick 2: Spreading Unbalanced representation of bipartite graphs B A We can split the bits as evenly as possible In particular, if |A|=|B|=n/2, we get a labeling scheme for balanced bipartite graphs with L = n/4 + lgn
Trick 2: Spreading Unbalanced representation of bipartite graphs B A
n + O(1) for directed graphs A B Use Trick 1 to represent A B This assigns indices to vertices of B (Cannot use Trick 1 again to represent B A) Use Trick 2, with bi = li + k, to represent B A
n/2 + O(1) for undirected graphs A0 A1 B0 B1
Concluding remarks Our essentially optimal adjacency labeling schemes yield essentially optimal induced-universal graphs Using a few more tricks we get down to n+3 for directed graphs, and n/2 +4 for undirected graphs More work needed for bipartite graphs, when the size of the sides is not fixed in advance Small additive gaps remain Improved lower bounds? All our schemes still assign vertices unique indices Not clear whether this is needed Optimal labeling schemes for other families? (E.g., graphs excluding a fixed minor, planar graphs, outerplanar graphs, bounded tree width, trees, etc.)
