Streaming Algorithms for Independent Sets in Sparse Hypergraphs

Bjarni V. Halldórsson, Magnús M. Halldórsson*, Elena Losievskaja, Mario Szegedy

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

We give the first treatment of the classic independent set problem in graphs and hypergraphs in the streaming setting. The objective is to find space-efficient algorithms that output independent sets that are “combinatorially optimal”, that is, with size guarantee in terms of the degree sequence alone. Our main result is a randomized algorithm that achieves this using space in bits that is linear in the number of vertices. We use this to examine assumptions about the streaming model, and advocate the study of output-efficient algorithms that measure space usage relative to the size of the output solution. In that sense, our main algorithm uses space linear in the output size. We also examine algorithms that use little or no space in addition to the bits storing the output. Our algorithms fall also into an online streaming model, where output-changes can go only in one direction. In particular a feasible solution must be maintained at all times, and items that are removed from the solution can never reenter. We obtain tight bounds on deterministic algorithms for independent sets in graphs in that model.

Original languageEnglish
Pages (from-to)490-501
Number of pages12
JournalAlgorithmica
Volume76
Issue number2
DOIs
Publication statusPublished - 1 Oct 2016

Bibliographical note

Publisher Copyright:
© 2015, Springer Science+Business Media New York.

Other keywords

  • Independent sets
  • Online streaming
  • Streaming algorithms
  • Turan bound

Fingerprint

Dive into the research topics of 'Streaming Algorithms for Independent Sets in Sparse Hypergraphs'. Together they form a unique fingerprint.

Cite this