我们关注图划分问题的两个变体：连接划分和密集划分。形式上，给定一个图 $G=(V,E)$ 及其顶点划分 $\mathcal P=\{P_1,\ldots, P_k\}$，当且仅当每个 $P_i$ 在 $G$ 中诱导出一个连通图时，我们称 $\mathcal P$ 为 $G$ 的连接划分。许多经典变体对部分数和每部分的大小施加额外限制。
另外，给定一个划分 $\mathcal P=\{P_1,\ldots, P_k\}$，我们定义其密度为 $d(\mathcal P):=\sum_{i=1}^k |E(P_i)|/|V(P_i)|$。最大密集图划分问题要求构建一个最大密度的划分。我们研究了这一问题，无论是固定集合数 $k$ 还是不固定。
我们证明了以下结果：
- 对于厚森林（一个和弦图的子类），我们提出了最大密集图划分的多项式时间算法，推广了已知的在块图上的多项式时间算法。
- 一个通用的动态规划算法，用于在具有有限树宽的图上构造（如果可能）具有预定大小的 $k$ 个集合的连接划分。这为密集图划分的两个变体提供了算法，并有效构造了 Győri-Lovász 定理。
- 在限制于分裂图的情况下，最大密集图划分到 $k$ 部分是 $\mathrm{NP}$-困难的，表明厚树是该问题多项式可计算性的边界。
博主点评： 本文在图划分领域提供了重要的理论进展，特别是动态规划算法的引入为密集划分问题的解决提供了新的思路。通过对厚森林的研究，明确了不同图类的计算复杂性，具有重要的应用价值。尽管在特定情况下存在多项式时间算法，但在更广泛的图类中，问题的复杂性依然挑战重重。