Uniform sampling of bi-colored random graph

Abstract

We propose a near-linear complexity algorithm for uniform sampling of simple random graphs with bi-colored edges imposed by two given colored degree sequences. This problem is also known as three-colour discrete tomography and is closely related to the sequence packing problem, both of which are known to be NP hard in the general setting. That being said, our algorithm provides a fast means of asymptotically uniform sampling for large graphs.