将超图划分为超森林

《Discrete Applied Mathematics》：Hypergraph partitioning into hyperforests

　　摘要
我们提出了一种使用超森林来寻找超图最小覆盖（划分）的算法。在更一般的情况下，给定与超边相关联的需求向量，我们寻找满足该需求的最小覆盖（划分）。这种方法用于将超图基阵多面体中的向量表示为超森林的关联向量的凸组合。

引言
图的树性是指其边集可以划分成的最小森林数量。对于一个（超）图??=(??,??)，一个子集?????和?????，让???[??]表示包含在??中的??的（超）边集。Nash-Williams [17]确立了树性的以下特征。

定理1 [16]
一个图??=(??,??)可以被划分成??个森林当且仅当对于每个节点集?????，有|???[??]|≤???(|??|?1)。因此，如果??=max?{|???[??]||??|?1:?????,|??|≥2}，定理1意味着树性是????。

图的森林概念被扩展到了超图上。对于一个超图??=(??,??)，如果对于所有?????都有???[??]≤|??|?1，则集合??是一个超森林（参见[9], [15]）。Frank等人[9]将定理1扩展到了超图上。

定理2 [9]
一个超图??=(??,??)可以被划分成??个超森林当且仅当对于每个节点集?????，有|???[??]|≤???(|??|?1)。

在这里，我们给出了一个将超图划分成超森林的算法。实际上，它提供了定理2的另一种证明方法。我们假设对于一个超图??=(??,??)，我们有一个需求向量??∈???+。我们用??(??)表示??的超森林集合。一个最小的整数划分是一个满足以下条件的解：
min?∑??∈??(??)????≥??，
对于每个超边??∈??，??≥0（整数值）。
一个最小的分数划分是一个满足(1)–(3)条件的解，不需要变量的整数性或需求的整数性。
如果对于所有??∈??都有???(??)=1，可以使用Edmonds的基阵划分算法[6]找到一个整数划分。然而，对于一般需求或分数情况，这并不能产生多项式时间算法。Frank [8]在他的书中提供了定理9.4.4的算法证明。这为所有需求都等于1的情况提供了一个算法。然而，他没有分析算法的复杂性，也不清楚这种方法是否可以扩展到一般需求的多项式时间算法。

树性可以在更一般的次模函数框架内进行研究，为各种图覆盖和划分结果提供了一个统一的视角。在这种情况下，一个关键的算法工具是次模函数最小化。关于这个主题的标准参考文献包括Frank的书[8]和Fujishige的专论[10]。
对于图，计算树性的算法已在[12], [13], [19]中提出，而计算划分的算法可以在[11], [18]中找到。最近在[3]中开发了计算树性的快速算法。将这些技术扩展到超图似乎更具挑战性，超出了本文的范围。

在这项工作中，我们讨论了超图的整数划分和分数划分。这些算法非常相似。我们使用分数划分算法将超图基阵多面体中的向量表示为极点的凸组合。

本文的结构如下：第2节提供定义和基本结果。第3节致力于计算树性。第4节讨论了划分的计算。第5节展示了如何将超图基阵多面体中的向量表示为极点的凸组合。

预备知识
在这里，我们提供定义并总结了一些基本结果。设??=(??,??)是一个超图。对于一个非空集合?????和?????，???[??]表示包含在??中的??的边集。设??={??1,…,????}是??的一个划分，我们用?????(??)表示在??中至少与两个集合相交的超边集合。对于一个超图??′=(??,??′)，有时我们使用????′?(??)代替????′?(??)。同样，当不会引起混淆时，我们使用???(??)代替?????(??)。如果对于所有?????，都有???(??,?????)≠0?（0?≠??≠??），我们说??是连通的。

计算树性
对于图，计算树性的算法已在[12], [13], [19]中提出，而将图划分为森林的算法可以在[11], [18]中找到。在本节中，我们描述了一个计算超图??=(??,??)树性的算法（也见于[1]）。给定一个需求向量??∈???+，我们需要计算max????(???[??])|??|?1，对于所有?????且|??|≥2。我们使用牛顿法如下：由于??的定义，我们总有???(???[???])????(∣???∣?1)≥0。如果??1,…,????是序列...

简化为打包超树
这里我们假设超图是连通的。如果不是，则应独立处理每个连通分量。为了解决(1)–(3)，我们首先增加需求??以将问题转化为打包超树的问题。然后我们应用[2]中描述的超树打包算法。首先我们需要像(10)中那样计算??，然后使用??′=????应用下面的算法。为了计算第3行中的???(??)，我们将??缩放到一个单节点???，并按照...

将向量表示为超图基阵多面体中的极点凸组合
对于基础集??上的一个基阵??，让???(??)表示其独立集的关联向量的凸包。Edmonds [7]给出了???(??)的明确描述：
定理13 [7]
???(??)={??∈???∣??≥0,???(??)≤???(??)，对于所有?????}。
对于一个超图??=(??,??)，设??是其相关的超图基阵，让???∈???(??)。在[1]中给出了一个测试向量是否满足(13)中不等式的算法。我们现在展示如何使用之前介绍的算法来表示???为凸组合。

Mourad Ba?ou | Francisco Barahona | CNRS