Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.52.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Sepehr Assadi
Sanjeev Khanna
Yang Li
Val Tannen

Cite As Get BibTex

Sepehr Assadi, Sanjeev Khanna, Yang Li, and Val Tannen. Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 52-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.FSTTCS.2015.52

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.

Subject Classification

Keywords
  • Small-space Algorithms
  • Maximum Matchings
  • Vertex Sparsifiers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Farid M. Ablayev. Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theor. Comput. Sci., 157(2):139-159, 1996. Google Scholar
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 459-467, 2012. Google Scholar
  3. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pages 5-14, 2012. Google Scholar
  4. Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer. Towards (1+ε)-approximate flow sparsifiers. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 279-293, 2014. Google Scholar
  5. Sepehr Assadi, Sanjeev Khanna, Yang Li, and Val Tannen. Dynamic sketching for graph optimization problems with applications to cut-preserving sketches. CoRR, abs/1510.03252, 2015. Google Scholar
  6. Moses Charikar, Tom Leighton, Shi Li, and Ankur Moitra. Vertex sparsifiers and abstract rounding algorithms. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 265-274, 2010. Google Scholar
  7. Julia Chuzhoy. On vertex sparsifiers with steiner nodes. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC, pages 673-688, 2012. Google Scholar
  8. Daniel Deutch, Zachary G. Ives, Tova Milo, and Val Tannen. Caravan: Provisioning for what-if analysis. In Sixth Biennial Conference on Innovative Data Systems Research, CIDR, 2013. Google Scholar
  9. Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, and Kunal Talwar. Vertex sparsifiers: New results from old techniques. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX, and 14th International Workshop, RANDOM, pages 152-165, 2010. Google Scholar
  10. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. In Automata, Languages and Programming: 31st International Colloquium, ICALP, pages 531-543, 2004. Google Scholar
  11. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct pcps for NP. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC, pages 133-142, 2008. Google Scholar
  12. Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde. Characterizing multiterminal flow networks and computing flows in networks of small treewidth. J. Comput. Syst. Sci., 57(3):366-375, 1998. Google Scholar
  13. Alan J Hoffman. Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In Proc. Sympos. Appl. Math, volume 10, pages 113-127. World Scientific, 1960. Google Scholar
  14. Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 561-570, 2014. Google Scholar
  15. Arindam Khan and Prasad Raghavendra. On mimicking networks representing minimum terminal cuts. Inf. Process. Lett., 114(7):365-371, 2014. Google Scholar
  16. Stefan Kratsch and Magnus Wahlström. Compression via matroids: a randomized polynomial kernel for odd cycle transversal. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 94-103, 2012. Google Scholar
  17. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 450-459, 2012. Google Scholar
  18. Robert Krauthgamer and Inbal Rika. Mimicking networks and succinct representations of terminal cuts. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1789-1799, 2013. Google Scholar
  19. Frank Thomson Leighton and Ankur Moitra. Extensions and limits to vertex sparsification. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC, pages 47-56, 2010. Google Scholar
  20. L. Lovász and D. Plummer. Matching Theory. AMS Chelsea Publishing Series. American Mathematical Soc., 2009. Google Scholar
  21. László Lovász. On determinants, matchings, and random algorithms. In FCT, pages 565-574, 1979. Google Scholar
  22. Dániel Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci., 410(44):4471-4479, 2009. Google Scholar
  23. Andrew McGregor. Graph stream algorithms: a survey. SIGMOD Record, 43(1):9-20, 2014. Google Scholar
  24. Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 3-12, 2009. Google Scholar
  25. S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, 1(2), 2005. Google Scholar
  26. Michael O. Rabin and Vijay V. Vazirani. Maximum matchings in general graphs through randomization. J. Algorithms, 10(4):557-567, 1989. Google Scholar
  27. Ronitt Rubinfeld and Asaf Shapira. Sublinear time algorithms. SIAM J. Discrete Math., 25(4):1562-1588, 2011. Google Scholar
  28. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003. Google Scholar
  29. William T Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, 1(2):107-111, 1947. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact