A Sequential Algorithm for Generating Random Graphs

We present the fastest FPRAS for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence

$(d_i)_{i=1}^n$

with maximum degree

$d_{\max}=O(m^{1/4-\tau})$

, our algorithm generates almost uniform random graph with that degree sequence in time

O

(

m

d

max

) where

is the number of edges in the graph and

τ

is any positive constant. The fastest known FPRAS for this problem [22] has running time of

O

(

m

3

n

2

). Our method also gives an independent proof of McKay’s estimate [33] for the number of such graphs.

Our approach is based on

sequential importance sampling

(SIS) technique that has been recently successful for counting graphs [15,11,10]. Unfortunately validity of the SIS method is only known through simulations and our work together with [10] are the first results that analyze the performance of this method.

Moreover, we show that for

d

 = 

O

(

n

1/2 − 

τ

), our algorithm can generate an asymptotically uniform

d

-regular graph. Our results are improving the previous bound of

d

 = 

O

(

n

1/3 − 

τ

) due to Kim and Vu [30] for regular graphs.