2026/07/24 by Katrin Casel, Archontia C. Giannopoulou, Aikaterini Niklanovits
#cs.DS
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=\P1,…, Pk\ we say that \mathcal P is a connected partition of G if each Pi induces a connected graph in G. Many classical variants of this problem impose additional restrictions both on the number of parts as well as on the size of each part. Moreover, given a partition \mathcal P=\P1,…, Pk\ we define its density by d(\mathcal P):=∑i=1k |E(Pi)|/|V(Pi)|. The problem Maximum Dense Graph Partition asks to construct a partition of maximum density. We study this problem both with and without 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 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.