Putting your graphs on a diet: Centralized and distributed representations for classes of graphs

27^th October 2022, 16:15
Sebastian Wild

Abstract

This talk will discuss different models for space-efficient representations of graphs and how they relate.
The first model is that of succinct data structures, where all data is held centrally and the emphasis is on supporting certain queries (such as adjacency, degree, neighbors, but also (unweighted) shortest-path distance) efficiently while using close to the information-theoretic minimum of space. Such representations can be used as a drop-in replacement for an adjacency-list representation. I will present some recent results on permutation graphs along these lines and introduce the building blocks of space-efficient data structures used therein.

The second model is that of graph labeling schemes, where the graph is stored in a distributed fashion: Each vertex is assigned a label so that the query under consideration (e.g. adjacency) can be answered from only seeing the labels of the involved vertices. Labeling schemes for the adjacency query are also known as implicit graph representations, which are the subject of the recently refuted, long-standing Implicit Graph Conjecture (IGC). I will summarize our recent work on randomized graph labeling schemes and its connection to the IGC.

I will finally show an example where a centralized, succinct data structure uses strictly less space than any graph labeling scheme can achieve; this example thus exhibits an inherent space overhead for decentralized computation.

This talk is based on joint work with Nathaniel Harms and Viktor Zamaraev [1] and joint work with Konstantinos Tsakalidis and Viktor Zamaraev [2].

[1] “Randomized Communication and Implicit Graph Representations”, STOC 2022,
https://www.wild-inter.net/publications/harms-wild-zamaraev-2022
[2] “Succinct Permutation Graphs”, Algorithmica 2022,
https://www.wild-inter.net/publications/tsakalidis-wild-zamaraev-2022

Additional Materials

• https://www.wild-inter.net/publications/harms-wild-zamaraev-2022 https://www.wild-inter.net/publications/tsakalidis-wild-zamaraev-2022