On the enumeration of minimal non-pairwise compatibility graphs
On the enumeration of minimal non-pairwise compatibility graphs
复制标题
DOI：
10.1007/s10878-021-00799-x
复制
发表时间：
2021-09-01
影响因子：
1
通讯作者：
Nagamochi，Hiroshi
中科院分区：
文献类型：
--
作者：
Azam，Naveed Ahmed;Shurbevski，Aleksandar;Nagamochi，Hiroshi
一个图称为成对相容图（PCG），如果存在一个边加权树，其叶集是图的顶点集，并且图中两个顶点之间存在边当且仅当它们在树中的距离在给定的区间内。这是一个具有挑战性的任务，列举所有的非PCG是最小的意义上，他们的每个诱导子图是一个PCG，并提供这一事实的证明。首先，它涉及大量的组合决策有关的树和叶顶点对应的结构。此外，即使对于固定的树，也存在边权重的无限连续域。我们处理的组合问题，第一次筛选图，PCG使用启发式PCG生成器。然后，我们构造“配置”，显示一些图是PCG。最后，我们生成的配置，不包括那些不能用来表明一个给定的图是PCG。为了构造有限大小的证据，一个图是一个最小的非PCG在面对一个无限的搜索空间，我们使用线性规划（LP）配方，其解决方案作为证据。为了证明我们的方法，我们列举了所有最小的非PCG与九个顶点，这是未知的。我们证明了，正好有1494个最小的非PCG与9个顶点，并为他们每个人提供证据。
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.