Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time

This paper introduces average case analysis of fully dynamic graph connectivity (when the operations are edge insertions and deletions). To this end we introduce the model of stochastic graph processes, i.e. dynamically changing random graphs with random equiprobable edge insertions and deletions, which generalizes Erdös and Renyi’s 35 year-old random graph process. As the stochastic graph process continues indefinitely, all potential edge locations (in V × V) may be repeatedly inspected (and learned) by the algorithm. This learning of the structure seems to imply that traditional random graph analysis methods cannot be employed (since an observed edge is not a random event anymore). However, we show that a small (logarithmic) number of dynamic random updates are enough to allow our algorithm to re-examine edges as if they were random with respect to certain events (i.e. the graph “forgets” its structure). This short memory property of the stochastic graph process enables us to present an algorithm for graph connectivity which admits an amortized expected cost of O(log3 n) time per update. In contrast, the best known deterministic worst-case algorithms for fully dynamic connectivity require n1/2 time per update.

Duke Scholars

Author John H. Reif Computer Science