On the enumeration of minimal non-pairwise compatibility graphs

A graph is said to be a pairwise compatibility graph (PCG) if there exists an edge-weighted tree whose leaf set is the graph’s vertex set, and there exists an edge between two vertices in the graph if and only if the distance between them in the tree lies within a given interval. It is a challenging task to enumerate all non-PCGs that are minimal in the sense that each of their induced subgraphs is a PCG and deliver proof of this fact. First, it involves a large number of combinatorial decisions concerning the structure of a tree and leaf-vertex correspondence. Moreover, there exists an infinite continuous domain for the edge weights even for a fixed tree. We handle the combinatorial problem by first screening graphs that are PCGs using a heuristic PCG generator. Then, we construct “configurations” that show some graphs to be PCGs. Finally, we generate configurations without including those that cannot be used to show that a given graph is a PCG. In order to construct finite-sized evidence to a graph being a minimal non-PCG in the face of an infinite search space, we use linear programming (LP) formulations whose solutions serve as evidence. To demonstrate our approach, we enumerated all minimal non-PCGs with nine vertices, which were unknown. We prove that there are exactly 1494 minimal non-PCGs with nine vertices and provide evidence for each of them.