Optimal Bounds for Dominating Set in Graph Streams

on YouTube ↗42m

" summary

One-pass streaming Dominating Set on n-vertex graphs gets a constructive algorithm that uses Õ(n) space and returns an O(√n · polylog n)-approximation, with a phase transition at √n (below that space jumps to near-linear in input size). Allowing deletions removes the transition: any one-pass α-approximation on insertion–deletion streams needs Ω̃(n^2/α) space. Lower bound uses a random bipartite-clique hard distribution and an information-complexity reduction from Set-Union; upper bound matches via known edge-arrival set-cover methods.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:14Streaming Algorithms and Graph Streams Streaming Algorithms
3. 4:09Dominating Set and Set Cover
4. 5:49Streaming Algorithms for Set Cover
5. 8:18Streaming Algorithms for Dominating Sets
6. 10:41Leveraging Results from Set Cover to Dominating Set
7. 12:39Our Results 1. Algorithm for Insertion only Streams
8. 15:35Bipartite Incidence Graph Bipartite Incidence Graph Representation
9. 17:14Neighborhood-arrival Setting
10. 25:17Our Algorithm (2)
11. 30:43Lower Bound Technique
12. 35:13Hard Input Distribution (2)
13. 38:01Implementation of Idea
14. 40:39Conclusion Our Contribution