Graph Coupon Collector

In this paper we study the following covering process defined over an arbitrary directed graph. Each node is initially uncovered and is assigned a random integer rank drawn from a suitable range. The process then proceeds in rounds. In each round, a uniformly random node is selected and its lowest-ranked uncovered outgoing neighbor, if any, is covered. This process can be viewed as a variant of the classic coupon collector process.

We prove that if each node has in-degree Θ(d) and out-degree O(d), then with high probability, every node is covered within O(n + n log n / d) rounds, matching a lower bound due to Alon. Alon has also shown that, for a certain class of d-regular expander graphs, the upper bound holds no matter what method is used to choose the uncovered neighbor. In contrast, we show that for arbitrary d-regular graphs, the method used to choose the uncovered neighbor can affect the cover time by more than a constant factor.

You can also view the related talk.

Papers

Nedialko B. Dimitrov and C. Greg Plaxton. Optimal Cover Time for a Graph-Based Coupon Collector Process. Journal of Discrete Algorithms, February, 2013, doi:10.1016/j.jda.2013.02.003

Nedialko B. Dimitrov and C. Greg Plaxton. Optimal Cover Time for a Graph-Based Coupon Collector Process. UT Austin, Technical Report T-05-01, January, 2005

Nedialko B. Dimitrov and C. Greg Plaxton. Optimal Cover Time for a Graph-Based Coupon Collector Process. Proceedings of the 32nd annual International Colloquium on Automata, Languages and Programming (ICALP05), July, 2005

Comments and Questions


Warning: Creating default object from empty value in /home/nedd/neddimitrov.org/modules/CGExtensions/CGExtensions.module.php on line 630
Add a comment

Add A Comment

Visual Captcha
Code in the picture:
Your Name(*):
Comment(*):
 


© Copyright 2004-2017 - Ned Dimitrov