Problem 74: Succinct Representation for Functions on Graphs

From Open Problems in Sublinear Algorithms
Revision as of 14:11, 15 January 2016 by 74.108.164.245 (talk)
Jump to: navigation, search
Suggested by Robert Krauthgamer
Source Baltimore 2016
Short link https://sublinear.info/74

Suppose we want to design a data structure that stores, for a given edge-weighted (undirected) graph G = (V,E_G,w_G), the values of the minimum st-cuts for all s,t \in V. A naive method is to construct a table containing the value for each pair, requiring O(|V|^2) space (machine words). Alternatively, one may construct a Gomory–Hu tree [GomoryH-61]. This is a tree T = (V,E_T,w_T), in which the minimum st-cut values are equal to those in G. Since T is a tree, it requires only O(|V|) space.

Thus for this problem, a very space-efficient data structure (perhaps even the best one) is itself a graph G', and it encodes the desired values in a natural manner, just compute the same function (min st-cut) on G'. But is this the case for all such functions on graphs, or is there a (natural) case where a potentially complicated data structure outperforms a graphical encoding? The question applies both to exact and approximate computations of the function.