Summary: In the 1970s, Győri and Lovász showed that for a \(k\)-connected \(n\)-vertex graph, a given set of terminal vertices \(t_1, \dots , t_k\) and natural numbers \(n_1, \dots , n_k\) satisfying \(\sum_{i=1}^k n_i = n\), a connected vertex partition \(S_1, \dots , S_k\) satisfying \(t_i \in S_i\) and \(|S_i| = n_i\) exists. However, polynomial time algorithms to actually compute such partitions are known so far only for \(k \le 4\). This motivates us to take a new approach and constrain this problem to particular graph classes instead of restricting the values of \(k\). More precisely, we consider \(k\)-connected chordal graphs and a broader class of graphs related to them. For the first class, we give an algorithm with \(\mathcal{O}(n^2)\) running time that solves the problem exactly, and for the second, an algorithm with \(\mathcal{O}(n^4)\) running time that deviates on at most one vertex from the required vertex partition sizes.
For the entire collection see [Zbl 1535.68010].