补可约一致超图

补可约一致超图

Complement Reducible Uniform Hypergraphs

https://docserv.uni-duesseldorf.de/servlets/DerivateServlet/Derivate-79630/Gurski_complement.pdf

摘要

我们研究了补可约图（称为余图，co-graphs）在 rr-一致超图上的推广。rr-余超图的运算包括两个给定 rr-余超图的不交并，以及联运算（join operation），后者在两个给定 rr-余超图的非空顶点子集之间插入所有基数为 rr 的超边。我们证明了 rr-余超图的原始图（primal graphs）是特殊的余图，且 rr-余超图在 rr-一致超图的补运算下是封闭的。这导出了一种方法，用于判定输入的超图 HH 是否为 rr-余超图。若判定结果为是，我们能在多项式时间内找到 HH 的分解树。我们给出了具体公式，用于计算由两个 rr-一致超图的不交并以及两个 rr-一致超图的联运算所定义的 rr-一致超图的若干参数。所考虑的参数包括：最大稳定集的大小、最大余稳定集的大小、最大独立集的大小、最大余独立集的大小、最小顶点覆盖的大小、最小 2-横贯集（2-transversal）的大小、最小支配集的大小、强色数以及上色数。这使得我们能够在给定分解树的情况下，在 nn 个顶点的 rr-余超图上以

的时间复杂度计算这些数值。此外，我们总结了限制在 rr-余超图上的这些参数之间的关系。我们的方法推广并重新证明了关于余图的若干已知结果。

关键词： 超图；一致超图；余图；rr-余超图；算法；特殊图类

1. 引言

超图是高级研究中常用的基本数据结构，用于表示和分析复杂的大型数据集。超图是图的一种直接扩展，其中一条边可以连接任意数量的顶点，这意味着它是一种比普通图提供更多建模可能性的数据结构。超图有助于描述应用科学中的各种情况，例如化学 [1,2]、流行病 [3]、蛋白质-蛋白质相互作用 [4] 以及超图学习 [5,6]。更多的应用可以在 [7]（第 7 章）中找到。从理论角度来看，超图也非常有趣。关于超图上各种染色问题的众多结果，参见 [8]（第 11 章）和 [9]。

补可约图类（简称余图，co-graphs）自 20 世纪 70 年代起就在 [10–12] 中被研究，这类图可以通过对单顶点图进行补运算和不交并来构造。关于该类最早的综合研究之一可以在 [13] 中找到。余图正是那些不包含四顶点路径作为导出子图的图 [13]。余图引出了一类在大量应用中出现的图，参见 [13–16]。当限制在余图上时，许多困难的图问题可以在在线性时间内解决 [13,17]。余图已被推广到有向余图 [18,19]，后者在遗传学领域也有应用，参见 [20,21]。如果许多困难的有向图问题被限制在有向余图上，它们也可以在线性时间内解决 [22,23]。

2. 预备知识

2.1. 图

2.2. 余图 (Co-Graphs)

余图（co-graph），或称为补可约图（complement reducible graph），是指可以通过对单顶点图进行补运算和不交并而构造出来的图，参见 [13]。余图有几种等价的刻画。从算法的角度来看，我们要回顾的是，余图可以通过以下两种运算从单顶点图定义出来。设

为两个顶点不交的图。

根据给定的定义，每个余图（co-graph）都可以用一种树形结构来描述，这种结构被称为 co-tree（余树）。co-tree 的叶子节点对应于余图的顶点，而 co-tree 的内部节点对应于由子树定义的子表达式上所执行的操作。

2.3. 超图

因此，如果关联的原始图

是连通的或者分别具有 rr 个连通分量，则称超图 HH是连通的或者具有 rr 个连通分量。

3. r-余超图

4. r-余超图上的算法

在随后的小节（第 4.1–4.9 节）中，我们展示了具体的公式，用于计算由两个 rr-一致超图的二元不交并和联运算所定义的 rr-一致超图的若干图参数。在最后的小节（第 4.10 节）中，我们应用这些公式来比较所考虑的参数，并得出结论：当限制在由不交并和联运算定义的 rr-一致超图（从而在 rr-余超图）上时，这些参数可以在多项式时间内计算。

4.1. 最大稳定集

5. 结论与展望

除了所考虑的图参数之外，还有一些所谓的结构参数（structural parameters），它们衡量的是图分解为树结构时的结构。对于图而言，树宽（tree-width）[33] 和团宽（clique-width）[34] 是最重要的结构参数。

此外，余图以及有向余图都有大量的实际应用，参见 [13–16] 和 [20,21]。仍有待确定 rr-余超图的实际应用。