Latest revision |
Your text |
Line 1: |
Line 1: |
| {{Header | | {{Header |
| + | |title=Title of the problem |
| |source=baltimore16 | | |source=baltimore16 |
| |who=Robert Krauthgamer | | |who=Robert Krauthgamer |
| }} | | }} |
− | 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$.
| + | The open problem will appear here. |
− | 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 {{cite|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.
| |
− | | |
− | '''Some relevant examples:'''
| |
− | | |
− | * A randomized data structure for $(1+\varepsilon)$-approximating any cut value (or Rayleigh quotient) in $G$, which is more space-efficient than the known graphical representation, can be found in {{cite|AndoniCKQWZ-16}}.
| |
− | | |
− | * For a given graph $G$ with $k$ terminals, the exact values of all the minimum cuts between subsets of terminals can be stored simply as a list of $2^k$ numbers. The best graphical representation known is of size roughly $2^{2^k}$ {{cite|HagerupKNR-98|KhanR-14}}.
| |
− | | |
− | * A deterministic data structure for $(1+\varepsilon)$-approximating any multicommodity flow on a set of $k$ given terminals in $G$. There is no known graphical representation for this, whose size depends on $k$ and $\varepsilon$, but not on $G$ {{cite|AndoniGK-14}}.
| |