Ruling Sets in Random Order and Adversarial Streams

Sepehr Assadi, Aditi DudejaDISC 2021 · DOI

TL;DR

This paper tackles the problem of finding "ruling sets" in large graphs, which are crucial for breaking symmetry in distributed systems. The authors present new, more efficient algorithms for finding these sets in both adversarial and random-order data streams, significantly improving upon previous work and establishing new theoretical limits.

What Problem Does This Paper Address?

Imagine you have a massive network, like a social network or a communication system, and you need to select a subset of nodes (vertices) that satisfy two conditions:

  1. Separation: Any two selected nodes must be "far apart" from each other (at least a certain distance).
  2. Coverage: Every node in the network must be "close" to at least one selected node (within a certain distance).

This is the essence of the (α, β)-ruling set problem. It's a fundamental problem in distributed computing, useful for tasks like distributed coloring or finding maximal independent sets (a special case where α=2, β=1). The challenge arises when dealing with massive graphs that don't fit into memory, requiring "streaming algorithms" that process data sequentially with limited memory. This paper focuses on two types of streaming scenarios:

  • Adversarial Streams: Edges arrive in an arbitrary, potentially worst-case order.
  • Random-Order Streams: Edges arrive in a random sequence, which can sometimes simplify problems.

The authors aim to find more space-efficient algorithms for computing ruling sets in these streaming models, especially for the (2, 2)-ruling set problem, and to understand the fundamental limits of such algorithms.

Methods

The paper introduces several key algorithmic and theoretical contributions:

  • Random-Order Streams: The core idea is a "peeling decomposition" of the graph. This involves iteratively removing vertices with low degrees. By sampling vertices from these layers and then finding a Maximal Independent Set (MIS) on a carefully constructed subgraph, they achieve an O(n) space algorithm for (2, 2)-ruling sets. This is a significant improvement, as MIS itself can require much more space.
  • Adversarial Streams: For the more challenging adversarial setting, they adapt hierarchical sampling techniques. By carefully sampling sets of vertices and analyzing their degrees within the remaining graph, they develop an improved algorithm for (2, β)-ruling sets with O(β * n^(1 + 2/β - 1)) space. This leads to a notable improvement for the (2, 2)-ruling set case, reducing space complexity from O(n^(3/2)) to O(n^(4/3)).
  • Lower Bounds: To understand the limits, they construct a specific type of graph and use a reduction from the "Index" communication problem. This allows them to prove a lower bound of Ω(n²/α²) for computing (α, α-1)-ruling sets in adversarial streams for even α > 2, showing that certain ruling set problems are inherently hard to solve with limited space.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and lower bounds for general graphs, not specific datasets.

Key Insights and Ideas

  • Peeling Decomposition for Randomness: The paper shows that a graph's structure, when viewed through a "peeling" lens (iteratively removing low-degree vertices), can be effectively exploited in random-order streams. This decomposition, combined with random sampling, allows for efficient ruling set computation.
  • Bridging Distributed and Streaming Models: The techniques used, particularly the peeling decomposition, have roots in distributed graph algorithms. The paper demonstrates how these ideas can be adapted and improved for the streaming model.
  • Trade-off between Randomness and Adversariality: The results highlight a significant difference in complexity between random-order and adversarial streams. While ruling sets can be found with near-linear space in random streams, adversarial streams impose much stronger space requirements.
  • Fundamental Limits of Ruling Sets: The lower bound for (α, α-1)-ruling sets proves that for certain parameter choices, achieving a truly "sublinear" space algorithm (significantly less than the input size) is impossible, even with randomization.

Key Results

  • Random-Order Streams: An O(n) space semi-streaming algorithm for computing (2, 2)-ruling sets (and thus (2, β)-ruling sets for β ≥ 2). This is optimal in terms of space complexity.
  • Adversarial Streams: An improved O(β * n^(1 + 2/β - 1)) space streaming algorithm for (2, β)-ruling sets. This yields an O(n^(4/3)) space algorithm for (2, 2)-ruling sets, improving upon the previous best of O(n^(3/2)).
  • Lower Bound: A Ω(n²/α²) space lower bound for randomized one-pass streaming algorithms computing (α, α-1)-ruling sets in adversarial streams for any even α > 2.

Limitations and Future Work

  • Specific Ruling Set Types: While the paper provides algorithms for (2, 2) and general (2, β) ruling sets, and lower bounds for (α, α-1) ruling sets, the complexity for other (α, β) pairs in adversarial streams remains an open area.
  • Random-Order MIS: The paper notes that while their random-order ruling set algorithm is efficient, the complexity of computing MIS in random-order streams is still an open question.
  • Practical Performance: The algorithms are presented with theoretical space complexity bounds. Their practical performance on real-world large-scale graphs would require empirical evaluation.
  • Generalization: Extending the techniques to other types of graph parameters or more complex ruling set definitions could be a future direction.

Summary updated

BibTeX
@inproceedings{assadi2021ruling,
  author = {Sepehr Assadi and Aditi Dudeja},
  title = {{Ruling Sets in Random Order and Adversarial Streams}},
  booktitle = {DISC},
  year = {2021},
  doi = {10.4230/lipics.disc.2021.6},
}
Figure