Difference between revisions of "Open Problems:74"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Small edits)
Line 4: Line 4:
 
|who=Robert Krauthgamer
 
|who=Robert Krauthgamer
 
}}
 
}}
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$.
+
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 Gomory–Hu tree {{cite|GomoryH-61}}.
 
Alternatively, one may construct a Gomory–Hu tree {{cite|GomoryH-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.
+
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.
  
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.
+
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 another—potentially complicated—data structure could out-perform a graph?
+
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?

Revision as of 14:10, 15 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?