Problem 74: Succinct Representation for Functions on Graphs

From Open Problems in Sublinear Algorithms
Revision as of 18:09, 12 January 2016 by Ccanonne (talk | contribs)
Jump to: navigation, search
Suggested by Robert Krauthgamer
Source Baltimore 2016
Short link https://sublinear.info/74

Given an undirected graph $G = (V,E_G)$ with weight function $w_G$, one may wish to design a data structure to store the value of the minimum $s-t$ cut, for any $s,t \in V$. A naive method is to construct a table containing the value for each pair, requiring $O(|V|^2)$ space. Alternatively, one may construct a Gomory-Hu tree [GomoryHu-61]. This is an undirected tree $T = (V,E_T)$ with weight function $w_T$, such that the minimum $s-t$ cut values from $G$ are preserved. Since $T$ is a tree, it requires only $O(|V|)$ space.

For this problem, it turns out the most space-efficient data structure is a graph which preserves the value of the function we wish to query. But is this the case for all such functions on graphs, or is there a (natural) case where another — potentially complicated — data structure could out-perform a graph?