Random generation of essential directed acyclic graphs

Abstract

A directed acyclic graph (DAG) is called essential if for every edge (u, v) it holds that the set of in-neighbors of u is different than the set of in-neighbors of v minus vertex u. Essential DAGs have applications in Bayesian networks, where a basic problem is to generate uniformly at random a labeled essential DAGs with a given number of vertices. In this paper we prove a new decomposition of essential DAGs, which entails: (i) a new counting recurrence, and (ii) a new random generation algorithm, that may be of potential use for their applications in Bayesian networks.