2026-07-22T14:20:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20585 2024-08-23T05:50:28Z ddc:004 open_access

Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats Lenstra Blažej, Václav Knop, Dušan Pokorný, Jan Schierreich, Šimon Equitable Connected Partition structural parameters fixed-parameter tractability N-fold integer programming tree-width shrub-depth modular-width In the Equitable Connected Partition (ECP for short) problem, 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. In this work, we systematically study ECP with respect to various structural restrictions of the underlying graph and provide a clear dichotomy of its parameterised complexity. Specifically, we show that the problem is in FPT when parameterized by the modular-width and the distance to clique. Next, we prove W[1]-hardness with respect to the distance to cluster, the 4-path vertex cover number, the distance to disjoint paths, and the feedback-edge set, and NP-hardness for constant shrub-depth graphs. Our hardness results are complemented by matching algorithmic upper-bounds: we give an XP algorithm for parameterisation by the tree-width and the distance to cluster. We also give an improved FPT algorithm for parameterisation by the vertex integrity and the first explicit FPT algorithm for the 3-path vertex cover number. The main ingredient of these algorithms is a formulation of ECP as N-fold IP, which clearly indicates that such formulations may, in certain scenarios, significantly outperform existing algorithms based on the famous algorithm of Lenstra. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Václav Blažej and Dušan Knop and Jan Pokorný and Šimon Schierreich 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.29 urn:nbn:de:0030-drops-205857 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.29 eng https://creativecommons.org/licenses/by/4.0/legalcode