Equitable Connected Partition and Structural Parameters Revisited: N-fold Beats Lenstra
<|reference_start|>Equitable Connected Partition and Structural Parameters Revisited: N-fold Beats Lenstra: 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 W[1]-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 W[1]-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 W[1]-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.<|reference_end|>
@article{blažej2024equitable,
    title={Equitable Connected Partition and Structural Parameters Revisited:
  N-fold Beats Lenstra},
    author={V'aclav Blav{z}ej and Duv{s}an Knop and Jan Pokorn'y and v{S}imon
  Schierreich},
    journal={arXiv preprint arXiv:2404.18968},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.18968},
    primaryClass={cs.DS}
}