具有顶点过剩的图的连通划分

《Discrete Applied Mathematics》：Connected partitions of graphs with vertex excess

　　**摘要**
在这项工作中，我们通过允许部分通过外部顶点来诱导连通图，从而推广了连通划分和任意可划分图的概念。具体来说，对于一个阶为$n$的图$G$及其任意划分$\pi=(n_1,\ldots,n_p)$，我们感兴趣的是$G^2$的划分$\Phi=(W_1,\ldots,W_p)$，其中对于所有$i \in \{1,\ldots,p\}$，都有$|W_i| = n_i$，并且存在（可能为空的）集合$\Gamma=(C_1,\ldots,C_p)$，使得对于每个$i \in \{1,\ldots,p\}$，$G^2[W_i \cup C_i]$都是连通的。也就是说，$C_i$中的顶点充当“辅助者”来使$W_i$诱导出连通图。然而，从实际角度来看，希望图$G$中的某个顶点不会出现在$\Gamma$的太多部分中，我们把这个参数称为其“过度使用”。我们引入并研究了新的概念$x-XAP$图，这类图无论$\pi$如何划分都能满足这个条件，并且每个顶点的过度使用都不超过$x$。我们开始研究这些概念，特别关注如何在不增加额外过度使用要求的情况下推广早期结果。我们确定了$x-XAP$图的几个性质，特别是对于这个领域中常见的图类。我们还提供了算法结果，证明了无论过度使用量如何，找到某个特定的$\Phi$或$\Gamma$都是NP完全问题。最后，我们提出了进一步研究的方向。

**引言**
设$G$是一个阶为$n$的图（即有$n$个顶点）。一个$n$-划分$\pi=(n_1,\ldots,n_p)$是将$G$划分为$p \geq 1$个部分$n_1,\ldots,n_p$。一个$\pi$-实现$(W_1,\ldots,W_p)$是在$G^2$中的划分，使得对于每个$i \in \{1,\ldots,p\}$，$G^2[W_i]$都是连通的（即$G^2[W_i]$是连通的），并且对于所有$i \in \{1,\ldots,p\}$，都有$|W_i| = n_i$。最后，如果所有$n$-划分都可以在$G$中实现，我们称$G$是任意可划分的（简称AP图）；换句话说，如果$G$可以被（逐个顶点地）划分为任意多个连通图，无论它们的阶是多少。注意，一个图是AP图的一个必要且隐含的条件是它是连通的。
AP图的概念是由Barth、Baudon和Puech在[2]中独立提出的，Horňák和Wo?niak在[13]中也提出了这个概念。在前一个参考文献中，作者提出这个概念的原因是它模拟了以下实际问题：假设我们拥有$n$个计算资源，并且作为管理者，我们需要将这些资源在$p$个客户之间进行分配。当然，资源不应该被随意分割；相反，分配给某个客户的资源应该形成一个网络，即这些资源能够在它们形成的子网络内部进行通信。为了避免并发冲突，也不应该将任何资源分配给两个不同的客户。这个问题可以很自然地用图的形式来建模，其中我们的网络被表示为一个图（顶点代表资源，边表示资源对之间的直接通信），而上述资源共享问题对应于将这个图划分为连通的子图。由于我们事先无法知道客户的数量$p$以及他们请求的资源数量$n_1,\ldots,n_p$，理想情况下，我们 prefer 图形是一种AP图，这样就不会出现无法满足客户需求的糟糕情况。
自从引入AP图的概念以来，已经对其进行了多项研究，例如参见[3]、[8]、[9]、[10]、[14]和[17]，这些文献提供了该主题的最新进展概述。注意，后续的研究将回顾与我们自己的调查相关的先前结果。

尽管上述的实际网络共享问题相当自然，但它也相当普遍，因此有人可能会认为AP图的概念并不是最合适的建模方式。例如，有人可能会认为，一旦所有资源都被请求，就立即共享我们的网络并不太自然，因此更倾向于根据客户的请求动态分配资源。同样，也有人可能会认为，如果我们分配的所有子网络都可以根据需要递归共享，以便客户将来能够重新共享他们的网络。或者，在某些情况下，我们的资源可能并不完全相同，因此客户可能会要求他们的子网络包含某些特定的资源。这些考虑促使作者引入了更受限的AP图概念（如OLAP图[12]、RAP图[6]和AP+??图[5]），研究这些修改后的概念与原始概念之间的差异也很有意义。
在这项工作中，我们引入了另一种修改后的AP图概念，其灵感来源于以下思考：显然，并非所有图都是AP图；例如，考虑在任何阶为$n \geq 4$的星形图中实现$n$-划分(2,…,2)。这表明，在我们之前提到的实际问题中，根据网络的结构和客户的请求，我们可能无法满足所有客户的期望。在这种情况下，我们可能会尝试尽可能最大化客户的满意度，同时尽量减少干扰/不满。同样，这些目标相当模糊，我们可以想象几种衡量满意度/不满的方法。
在这里，我们关注以下想法和概念，我们认为这些是考虑原始实际问题时最自然的概念。在将资源分配给客户$Q_1$时，理想的情景是这些资源形成一个子网络$N_1$，其中任意两个资源都可以通信（不一定是直接的），从图论的角度来看，这相当于连通性。然而，在这些资源不能形成这样的子网络的情况下（即，等价地说，形成了一个不连通的子图），$N_1$中希望通信的任意两个资源可能需要依赖属于其他客户$Q_2,\ldots,Q_p$的网络中的资源作为中间件。从$Q_1$的角度来看，允许这样的外部通信是透明的，因此是可以接受的。然而，如果$N_2,\ldots,N_p$中的资源支持$N_1$中的资源之间的通信，可能会导致$N_2,\ldots,N_p$中的资源承担额外的工作负载，从而给$N_2,\ldots,N_p$的子网络带来不便（如减速等）。因此，尽管允许这样的外部通信是可行的，但应该对其加以限制。
我们通过以下术语来处理这些担忧（见图1）。设$G$是一个阶为$n$的图，设$\pi=(n_1,\ldots,n_p)$是一个$n$-划分，设$\Phi=(W_1,\ldots,W_p)$是将$G^2$划分为$p$个部分$W_1,\ldots,W_p$的划分，其中$W_i$的基数分别为$n_1,\ldots,n_p$，这些部分不一定是连通的。一个集合$\Gamma=(C_1,\ldots,C_p)$是$G^2$的$p$个（可能为空且/或相交的）子集$C_1,\ldots,C_p$的集合，如果对于所有$i \in \{1,\ldots,p\}$，都有$G^2[W_i \cup C_i]$是连通的，则称$\Gamma$为$\Phi-$连接器。如果$\Gamma$是一个$\Phi-$连接器，那么我们称$(\Phi,\Gamma)$为$G$中的一个$\pi$-实现。也就是说，$\Phi$可能不是一个$\pi$-实现（如果某些$W_i$是不连通的），但当添加$\Gamma$中的顶点后，每个不连通的$W_i$部分就变得连通了。关于上述担忧，简单来说，连接器中的任何部分$C_i$都表示支持$W_i$中资源之间通信的中间资源。显然，如果$\Gamma=0^\infty$，那么$W_i$是连通的。实际上，如果$\Phi$已经是一个$\pi$-实现，那么$\Gamma=(0^\infty,\ldots,0^\infty)$就是一个$\Phi-$连接器。正如前面提到的，我们更感兴趣的是那些不会过多涉及某些特定顶点的连接器。也就是说，$G$中的每个顶点$u$在某种意义上是“更紧张”的，这取决于包含$u$的$\Gamma$的数量。也就是说，包含$u$的$\Gamma$越多，$u$在帮助连接不连通的部分方面就越有帮助。关于$\Gamma$，我们用$x^2(u) \geq 0$表示$u$的“过度使用”，即$\Gamma$中包含$u$的$\Gamma$的数量。同样，我们用$x^2(\Phi,\Gamma)$表示$(\Phi,\Gamma)$的“过度使用”，即最小的$x \geq 0$，使得对于$G$中的所有顶点$u$，都有$x^2(u) \leq x$。由于我们希望尽量最小化这个参数，我们说$G$是$x-XAP$图，如果$x \geq 0$是每个$n$-划分都允许具有最多$x$过度使用的实现的最小整数。注意，AP性正是0-XAP性。

**工作组织**
我们的工作安排如下：第2节首先对我们刚刚介绍的所有概念提出了一些初步的评论和观察。特别是在那里，我们提出了猜想2.7，关于图是$x-XAP$图的最大值$x$。然后我们在第3节进一步研究了这个猜想，针对该领域中的一些常见图类。我们在第4节用算法结果补充了我们的结果。特别是，我们证明了在一个图中，实现给定的划分并具有给定的过度使用量，以及找到具有给定过度使用量的连接器，都是NP完全问题。第5节我们提出了一些问题，这些问题的进一步研究可能会很有吸引力。

**章节片段**
**初步评论、观察和问题**
首先，我们陈述一个显而易见的事实：如果我们不介意最小化最终的过度使用量，那么对于每个阶为$n$的连通图$G$，每个$n$-划分都可以在$G$中实现。
**观察2.1**
如果$G$是一个阶为$n$的连通图，且$\pi$是一个$n$-划分，那么在$G$中存在$\pi$-实现（$\Phi,\Gamma$）（因此有一定的过度使用）。

**证明**
只需考虑$G^2$的任何划分$\Phi=(W_1,\ldots,W_p)$，其中（不一定是连通的）部分的基数满足$\pi$的要求，并考虑$\Gamma=(C_1,\ldots,C_p)$。

**图类**
在本节中，我们研究了在研究AP图时常见的图类的XAP性。我们在这里建立的所有结果都应该在猜想2.7的背景下考虑，我们基本上确认了所有我们考虑的图类都满足这个猜想。关注特定图类的另一个关键点是以下对AP图的一个关键结果的明显推广（参见例如[2]）：
**观察3.1**
对于任何$x \geq 0$，如果$G$是一个由$x-XAP$图生成的图，那么$G$是...

**算法结果**
在本节中，我们提供了关于图XAP性相关问题复杂性的几个结果。谈到AP图背后的原始概念，也许最自然要考虑的两个问题是：
- **实现实例**：一个阶为$n$的图$G$和一个$n$-划分$\pi=(n_1,\ldots,n_p)$。
问题：$G$是否允许一个$\pi$-实现$(W_1,\ldots,W_p)$？
- **AP实例**：图$G$。
问题：$G$是否是AP图？

**结论和展望**
出于实际考虑的动机，我们通过引入顶点过度使用的概念，推广了连通划分和AP图的概念，其中本质上，我们允许实现的部分不一定是连通的，只要我们提供外部顶点来支持连通性。正如引言部分所解释的，从实际角度来看这是合理的。正如观察2.1所示，允许过度使用可以预期地使得图可以被划分为任意多个连通的部分。

**Olivier Baudon | Julien Bensmail | Lyn Vayssieres**