Equitable Connected Partition and Structural Parameters Revisited: N-fold Beats Lenstra

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00375730" target="_blank" >RIV/68407700:21240/24:00375730 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.29" target="_blank" >https://doi.org/10.4230/LIPIcs.MFCS.2024.29</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2024.29" target="_blank" >10.4230/LIPIcs.MFCS.2024.29</a>

Result language

angličtina

Original language name

Equitable Connected Partition and Structural Parameters Revisited: N-fold Beats Lenstra

Original language description

In the Equitable Connected Partition (ECP for short) problem, we are given a graph $G=(V,E)$ together with an integer $pinmathbb{N}$, 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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science

ISBN

978-3-95977-335-5

ISSN

1868-8969

e-ISSN

—

Number of pages

16

Pages from-to

"29:1"-"29:16"

Publisher name

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Place of publication

—

Event location

Bratislava

Event date

Aug 26, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—