A Method to Generate Multi-interval Pairwise Compatibility Graphs

Abstract

Enumerating multi-interval pairwise compatibility graphs ([Formula: see text]-IPCGs) is computationally challenging due to the exponential growth in the number of graphs and trees, as well as the infinite search space for weights. Currently, no method exists to enumerate all [Formula: see text]-IPCGs for a given number of vertices. We prove that every [Formula: see text]-IPCG can be represented by a tree with all internal vertices of degree three, and we develop a dynamic programming algorithm to enumerate such trees. We also propose the first [Formula: see text]-IPCG generator, based on the property that the smallest intervals for a [Formula: see text]-IPCG can be derived from the distances between the leaves of its tree representation. Our generator identifies [Formula: see text]-IPCGs with a given number of vertices by randomly assigning edge weights and constructing the smallest intervals. We implemented this generator to identify two-interval PCGs (2-IPCGs) with up to ten vertices, for which the structure and count were previously unknown. Our results show that there exist four, six, and eleven trees, with all internal vertices having degree exactly three, and with eight, nine, and ten leaves, respectively. This significantly reduces the exponential search space of the tree. We further demonstrate that all graphs with up to ten vertices are 2-IPCGs, making progress toward the open problem of identifying the smallest non-2-IPCG and providing a basis for phylogenetics to test whether a small graph is a [Formula: see text]-IPCG.