King's College London

Research portal

New Cover Time Bounds for the Coalescing-Branching Random Walk on Graphs

Research output: Contribution to journalArticlepeer-review

Original languageEnglish
Article number16
Pages (from-to)1-24
Number of pages24
JournalACM Transactions on Parallel Computing
Volume6
Issue number3
Early online date30 Nov 2019
DOIs
Accepted/In press5 Aug 2019
E-pub ahead of print30 Nov 2019
PublishedDec 2019

Documents

King's Authors

Abstract

We present new bounds on the cover time of the coalescing-branching random walk process COBRA. The COBRA process, introduced in Dutta et al. [9], can be viewed as spreading a single item of information throughout an undirected graph in synchronised rounds. In each round, each vertex that has received the information in the previous round (possibly simultaneously from more than one neighbour and possibly not for the first time), "pushes" the information to k randomly selected neighbours. The COBRA process is typically studied for integer branching rates k ≥ 2 (with the case k = 1 corresponding to a random walk). The aim of the process is to propagate the information quickly, but with a limited number of transmissions per vertex per round. The COBRA cover time is the expected number of rounds until all vertices have received the information at least once. Our main results are bounds of O(m + (dmax)2 logn) and O(m logn) on the COBRA cover time for arbitrary connected graphs with n vertices, m edges and maximum graph degree dmax, and bounds of O((r 2 + r/(1 - λ)) logn) and O((1/(1 - λ)2) logn) for r -regular connected graphs with the second largest eigenvalue λ in absolute value. Our bounds for general graphs are always O(n2 logn), decreasing to O(n) for constant degree graphs, while the best previous bound is O(n2.75 logn). Our first bound for regular graphs applied to the lazy variant of the COBRA process is O((r 2 + r/φ2) logn), where φ is the conductance of the graph. The best previous results for the COBRA process imply for this case only a bound of O((r 4/φ2) log2 n). To derive our bounds, we develop the following new approach to analysing the performance of the COBRA process. We introduce a type of infection process, which we call the Biased Infection with Persistent Source (BIPS) process, show that BIPS can be viewed as dual to COBRA, and obtain bounds for COBRA by analysing the convergence of BIPS.

Download statistics

No data available

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454