title: Approximate Counting of Graphical Realizations.
abstract: In 1999 Kannan, Tetali and Vempala proposed a MCMC method to uniformly sample all possible realizations of a given graphical degree sequence and conjectured its rapidly mixing nature. Recently their conjecture was proved affirmative for regular graphs (by Cooper, Dyer and Greenhill, 2007), for regular directed graphs (by Greenhill, 2011) and for half-regular bipartite graphs (by Miklós, Erdős and Soukup, 2013). Several heuristics on counting the number of possible realizations exist (via sampling processes), and while they work well in practice, so far no approximation guarantees exist for such an approach. This paper is the first to develop a method for counting realizations with provable approximation guarantee. In fact, we solve a slightly more general problem; besides the graphical degree sequence a small set of forbidden edges is also given. We show that for the general problem (which contains the Greenhill problem and the Miklós, Erdős and Soukup problem as special cases) the derived MCMC process is rapidly mixing. Further, we show that this new problem is self-reducible therefore it provides a fully polynomial randomized approximation scheme (a.k.a. FPRAS) for counting of all realizations.
authors.affiliation: Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary.
authors.forename: Péter L
authors.initials: PL
authors.lastname: Erdős
authors.affiliation: Institute for Computer Science and Control, Hungarian Academy of Sciences, Budapest, Hungary; Department of Algebra, University of Technology and Economics, Budapest, Hungary.
authors.forename: Sándor Z
authors.initials: SZ
authors.lastname: Kiss
authors.affiliation: Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary; Institute for Computer Science and Control, Hungarian Academy of Sciences, Budapest, Hungary.
authors.forename: István
authors.initials: I
authors.lastname: Miklós
authors.affiliation: Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary.
authors.forename: Lajos
authors.initials: L
authors.lastname: Soukup
mesh_terms: D000465:Algorithms; D003195:Computer Communication Networks; D003196:Computer Graphics; D003198:Computer Simulation; D008390:Markov Chains; D008962:Models, Theoretical; D012494:Sampling Studies