Connected (Dense) Partition for Tree-Like Graphs

Abstract

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,\dots ,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 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}=\{P_1,\dots ,P_k\}$ we define its density by $d(\mathcal{P}):={\sum }_{i=1}^k|E(P_i)|/|V(P_i)|$. 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 $\mathsf{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.

35 pages, 6 Figures