License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2015.52
URN: urn:nbn:de:0030-drops-56361
URL: https://drops.dagstuhl.de/opus/volltexte/2015/5636/
Go to the corresponding LIPIcs Volume Portal


Assadi, Sepehr ; Khanna, Sanjeev ; Li, Yang ; Tannen, Val

Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches

pdf-format:
21.pdf (0.5 MB)


Abstract

In this paper, we introduce a new model for sublinear algorithms called dynamic sketching. In this model, the underlying data is partitioned into a large static part and a small dynamic part and the goal is to compute a summary of the static part (i.e, a sketch) such that given any update for the dynamic part, one can combine it with the sketch to compute a given function. We say that a sketch is compact if its size is bounded by a polynomial function of the length of the dynamic data, (essentially) independent of the size of the static part. A graph optimization problem P in this model is defined as follows. The input is a graph G(V,E) and a set T \subseteq V of k terminals; the edges between the terminals are the dynamic part and the other edges in G are the static part. The goal is to summarize the graph G into a compact sketch (of size poly(k)) such that given any set Q of edges between the terminals, one can answer the problem P for the graph obtained by inserting all edges in Q to G, using only the sketch. We study the fundamental problem of computing a maximum matching and prove tight bounds on the sketch size. In particular, we show that there exists a (compact) dynamic sketch of size O(k^2) for the matching problem and any such sketch has to be of size \Omega(k^2). Our sketch for matchings can be further used to derive compact dynamic sketches for other fundamental graph problems involving cuts and connectivities. Interestingly, our sketch for matchings can also be used to give an elementary construction of a cut-preserving vertex sparsifier with space O(kC^2) for k-terminal graphs, which matches the best known upper bound; here C is the total capacity of the edges incident on the terminals. Additionally, we give an improved lower bound (in terms of C) of Omega(C/log{C}) on size of cut-preserving vertex sparsifiers, and establish that progress on dynamic sketching of the s-t max-flow problem (either upper bound or lower bound) immediately leads to better bounds for size of cut-preserving vertex sparsifiers.

BibTeX - Entry

@InProceedings{assadi_et_al:LIPIcs:2015:5636,
  author =	{Sepehr Assadi and Sanjeev Khanna and Yang Li and Val Tannen},
  title =	{{Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{52--68},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Prahladh Harsha and G. Ramalingam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5636},
  URN =		{urn:nbn:de:0030-drops-56361},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.52},
  annote =	{Keywords: Small-space Algorithms, Maximum Matchings, Vertex Sparsifiers}
}

Keywords: Small-space Algorithms, Maximum Matchings, Vertex Sparsifiers
Seminar: 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Issue Date: 2015
Date of publication: 11.12.2015


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI