Independent Sets in Vertex-Arrival Streams

Authors Graham Cormode , Jacques Dark, Christian Konrad



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.45.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Graham Cormode
  • University of Warwick, UK
Jacques Dark
  • University of Warwick, UK
Christian Konrad
  • University of Bristol, UK

Cite AsGet BibTex

Graham Cormode, Jacques Dark, and Christian Konrad. Independent Sets in Vertex-Arrival Streams. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.45

Abstract

We consider the maximal and maximum independent set problems in three models of graph streams: - In the edge model we see a stream of edges which collectively define a graph; this model is well-studied for a variety of problems. We show that the space complexity for a one-pass streaming algorithm to find a maximal independent set is quadratic (i.e. we must store all edges). We further show that it is not much easier if we only require approximate maximality. This contrasts strongly with the other two vertex-based models, where one can greedily find an exact solution in only the space needed to store the independent set. - In the "explicit" vertex model, the input stream is a sequence of vertices making up the graph. Every vertex arrives along with its incident edges that connect to previously arrived vertices. Various graph problems require substantially less space to solve in this setting than in edge-arrival streams. We show that every one-pass c-approximation streaming algorithm for maximum independent set (MIS) on explicit vertex streams requires Omega({n^2}/{c^6}) bits of space, where n is the number of vertices of the input graph. It is already known that Theta~({n^2}/{c^2}) bits of space are necessary and sufficient in the edge arrival model (Halldórsson et al. 2012), thus the MIS problem is not significantly easier to solve under the explicit vertex arrival order assumption. Our result is proved via a reduction from a new multi-party communication problem closely related to pointer jumping. - In the "implicit" vertex model, the input stream consists of a sequence of objects, one per vertex. The algorithm is equipped with a function that maps pairs of objects to the presence or absence of edges, thus defining the graph. This model captures, for example, geometric intersection graphs such as unit disc graphs. Our final set of results consists of several improved upper and lower bounds for interval and square intersection graphs, in both explicit and implicit streams. In particular, we show a gap between the hardness of the explicit and implicit vertex models for interval graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Lower bounds and information complexity
  • Theory of computation → Streaming models
Keywords
  • streaming algorithms
  • independent set size
  • lower bounds

Metrics

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

References

  1. Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. Correlation Clustering in Data Streams. In Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37, ICML'15, pages 2237-2246. JMLR.org, 2015. URL: http://dl.acm.org/citation.cfm?id=3045118.3045356.
  2. Noga Alon, Ankur Moitra, and Benny Sudakov. Nearly Complete Graphs Decomposable into Large Induced Matchings and Their Applications. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 1079-1090, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2213977.2214074.
  3. Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Sublinear Algorithms for (Δ + 1) Vertex Coloring. In SODA, 2019. Google Scholar
  4. Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 1345-1364, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2884435.2884528.
  5. Béla Bollobás. The chromatic number of random graphs. Combinatorica, 8(1):49-55, 1988. Google Scholar
  6. Vladimir Braverman, Zaoxing Liu, Tejasvam Singh, N. V. Vinodchandran, and Lin F. Yang. New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory. Algorithmica, 80(2):652-667, February 2018. URL: http://dx.doi.org/10.1007/s00453-017-0277-5.
  7. Sergio Cabello and Pablo Pérez-Lantero. Interval selection in the streaming model. Theoretical Computer Science, 702:77-96, 2017. Google Scholar
  8. Amit Chakrabarti. Lower bounds for multi-player pointer jumping. In Computational Complexity, 2007. CCC'07. Twenty-Second Annual IEEE Conference on, pages 33-45. IEEE, 2007. Google Scholar
  9. Graham Cormode, Jacques Dark, and Christian Konrad. Approximating the Caro-Wei Bound for Independent Sets in Graph Streams. In Jon Lee, Giovanni Rinaldi, and A. Ridha Mahjoub, editors, Combinatorial Optimization, pages 101-114, Cham, 2018. Springer International Publishing. Google Scholar
  10. Graham Cormode, Jacques Dark, and Christian Konrad. Independent Sets in Vertex-Arrival Streams. CoRR, abs/1807.08331, 2018. URL: http://arxiv.org/abs/1807.08331.
  11. Yuval Emek, Magnús M Halldórsson, and Adi Rosén. Space-constrained interval selection. ACM Transactions on Algorithms (TALG), 12(4):51, 2016. Google Scholar
  12. Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 468-485, 2012. Google Scholar
  13. Bjarni V Halldórsson, Magnús M Halldórsson, Elena Losievskaja, and Mario Szegedy. Streaming algorithms for independent sets. In International Colloquium on Automata, Languages, and Programming, pages 641-652. Springer, 2010. Google Scholar
  14. Magnús M. Halldórsson and Christian Konrad. Computing Large Independent Sets in a Single Round. Distrib. Comput., 31(1):69-82, February 2018. URL: http://dx.doi.org/10.1007/s00446-017-0298-y.
  15. Magnús M Halldórsson, Xiaoming Sun, Mario Szegedy, and Chengu Wang. Streaming and communication complexity of clique approximation. In International Colloquium on Automata, Languages, and Programming, pages 449-460. Springer, 2012. Google Scholar
  16. R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972. Google Scholar
  17. Christian Konrad. Maximum Matching in Turnstile Streams. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015, pages 840-852, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. Google Scholar
  18. I. Kremer, N. Nisan, and D. Ron. On Randomized One-round Communication Complexity. computational complexity, 8(1):21-49, 1999. URL: http://dx.doi.org/10.1007/s000370050018.
  19. Andrew McGregor. Graph Stream Algorithms: A Survey. SIGMOD Rec., 43(1):9-20, May 2014. URL: http://dx.doi.org/10.1145/2627692.2627694.
  20. David Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing, 3(1):103-128, 2007. 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