Key points are not available for this paper at this time.
We study the Equitable Connected Partition (ECP for short) problem, where we are given a graph G=(V,E) together with an integer p, and our goal is to find a partition of V into p parts such that each part induces a connected sub-graph of G and the size of each two parts differs by at most 1. On the one hand, the problem is known to be NP-hard in general and W1-hard with respect to the path-width, the feedback-vertex set, and the number of parts p combined. On the other hand, fixed-parameter algorithms are known for parameters the vertex-integrity and the max leaf number. As our main contribution, we resolve a long-standing open question Enciso et al.; IWPEC '09 regarding the parameterisation by the tree-depth of the underlying graph. In particular, we show that ECP is W1-hard with respect to the 4-path vertex cover number, which is an even more restrictive structural parameter than the tree-depth. In addition to that, we show W1-hardness of the problem with respect to the feedback-edge set, the distance to disjoint paths, and NP-hardness with respect to the shrub-depth and the clique-width. On a positive note, we propose several novel fixed-parameter algorithms for various parameters that are bounded for dense graphs.
Blažej et al. (Mon,) studied this question.