# Difference between revisions of "Open Problems:74"

(Created page with "{{Header |title=Title of the problem |source=baltimore16 |who=Robert Krauthgamer }} The open problem will appear here.") |
|||

Line 1: | Line 1: | ||

{{Header | {{Header | ||

− | |title= | + | |title=Space-Efficient Storage for Functions on Graphs |

|source=baltimore16 | |source=baltimore16 | ||

|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$. | |

+ | 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 {{cite|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 case where another (potentially complicated) data structure could out-perform a graph? |

## Revision as of 05:00, 12 January 2016

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 case where another (potentially complicated) data structure could out-perform a graph?