License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.2
URN: urn:nbn:de:0030-drops-124090
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12409/
Krauthgamer, Robert
Sketching Graphs and Combinatorial Optimization (Invited Talk)
Abstract
Graph-sketching algorithms summarize an input graph G in a manner that suffices to later answer (perhaps approximately) one or more optimization problems on G, like distances, cuts, and matchings. Two famous examples are the Gomory-Hu tree, which represents all the minimum st-cuts in a graph G using a tree on the same vertex set V(G); and the cut-sparsifier of Benczúr and Karger, which is a sparse graph (often a reweighted subgraph) that approximates every cut in G within factor 1±ε. Another genre of these problems limits the queries to designated terminal vertices, denoted T ⊆ V(G), and the sketch size depends on |T| instead of |V(G)|.
The talk will survey this topic, particularly cut and flow problems such as the three examples above. Currently, most known sketches are based on a graph representation, often called edge and vertex sparsification, which leaves room for potential improvements like smaller storage by using another representation, and faster running time to answer a query. These algorithms employ a host of techniques, ranging from combinatorial methods, like graph partitioning and edge or vertex sampling, to standard tools in data-stream algorithms and in sparse recovery. There are also several lower bounds known, either combinatorial (for the graph representation) or based on communication complexity and information theory.
Many of the recent efforts focus on characterizing the tradeoff between accuracy and sketch size, yet many intriguing and very accessible problems are still open, and I will describe them in the talk.
BibTeX - Entry
@InProceedings{krauthgamer:LIPIcs:2020:12409,
author = {Robert Krauthgamer},
title = {{Sketching Graphs and Combinatorial Optimization (Invited Talk)}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {2:1--2:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12409},
URN = {urn:nbn:de:0030-drops-124090},
doi = {10.4230/LIPIcs.ICALP.2020.2},
annote = {Keywords: Sketching, edge sparsification, vertex sparsification, Gomory-Hu tree, mimicking networks, graph sampling, succinct data structures}
}
|
Keywords: |
|
Sketching, edge sparsification, vertex sparsification, Gomory-Hu tree, mimicking networks, graph sampling, succinct data structures |
|
Collection: |
|
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
29.06.2020 |
