Difference between revisions of "Open Problems:74"
(Updating header) |
|||
| (7 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|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$. | |
| − | A naive method is to construct a table containing the value for each pair, requiring $O(|V|^2)$ space. | + | 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 | + | Alternatively, one may construct a Gomory–Hu tree {{cite|GomoryH-61}}. |
| − | This is | + | 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. | 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 case where | + | 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}}. | ||
Latest revision as of 18:43, 18 January 2016
| 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.
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 [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}$ [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$ [AndoniGK-14].
