The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation

摘要

It is known that any chordal graph on n vertices can be represented as the intersection of n subtrees in a tree on n nodes (Gavril in J Comb Theory 16:47-56, 1974). This characterization has been recently used to generate random chordal graphs on n vertices by generating n subtrees of a tree on n nodes. The space (and thus time) complexity of an algorithm generating n subtrees of a tree on n nodes is at least the sum of the sizes of the generated subtrees. The determination of this sum was left as an open question in Seker et al. (Generation of random chordal graphs using subtrees of a tree. arXiv preprint arXiv:1810.13326, 2018). In this paper, we show that the sum of the sizes of n subtrees in a tree on n nodes is Theta(m root n). We also show that we can confine ourselves to contraction-minimal subtree intersection representations because they are sufficient to generate every chordal graph with strictly positive probability. Moreover, the sum of the sizes of the subtrees in a contraction-minimal representation is at most 2m + n. We use this result to derive the first linear-time random chordal graph generator. Based on contraction-minimal representations, we also derive connectivity-related structural properties of chordal graphs. Besides these theoretical results, we also conduct experiments to study the quality of the chordal graphs generated by our algorithm and compare them to those generated by existing methods from the literature. Our algorithm does not generate chordal graphs uniformly at random, which is a quite challenging open question, irrespective of the time complexity of the generator. However, our experimental study suggests that the generated graphs have a fairly varied structure as indicated by the sizes of maximal cliques. Furthermore, our algorithm is simple to implement and produces graphs with 10,000 vertices and 4 x 10(7) edges in less than one second on a laptop computer.