We focus on two variants of graph partitioning problems, connected partition and dense partition. Formally, given a graph $G=(V,E)$ and a partition of its vertices $\mathcal P=\{P_1,\ldots, P_k\}$, we say that $\mathcal P$ is a connected partition of $G$ if each $P_i$ induces a connected graph in $G$. Many classical variants impose additional restrictions on the number of parts as well as on the size of each part.
Moreover, given a partition $\mathcal P=\{P_1,\ldots, P_k\}$, we define its density by $d(\mathcal P):=\sum_{i=1}^k |E(P_i)|/|V(P_i)|$. The Maximum Dense Graph Partition problem asks to construct a partition of maximum density. We study this problem both with and without a fixed number of sets $k$.
We prove the following results: 1. A polynomial time algorithm for Maximum Dense Graph Partition of thick forests, a subclass of chordal graphs, generalizing the previously known polynomial time algorithm on block graphs. 2. A generic dynamic programming algorithm to construct (if possible) a connected partition into $k$ sets of prescribed sizes on graphs with bounded treewidth. This yields algorithms for both variants of Dense Graph Partition and an efficient construction for the Győri-Lovász theorem. 3. The $\mathrm{NP}$-hardness of Maximum Dense Graph Partition to $k$ parts restricted to split graphs, indicating that thick trees are the boundary for the polynomial computability of this problem.
Blogger's Review: This paper presents significant theoretical advancements in the field of graph partitioning, particularly with the introduction of dynamic programming algorithms offering new insights into dense partition problems. The study of thick forests clarifies the computational complexity across different graph classes and holds substantial application value. While polynomial-time algorithms exist in specific cases, the complexity of the problem remains daunting in broader graph classes.