Parameterized Complexity of Connected Network Microaggregation: The Role of Cluster Size
Data Structures and Algorithms
Summary
The authors study a problem in graph clustering where nodes must be grouped into connected clusters that meet size and distance rules. They find that the problem is easier to solve (fixed-parameter tractable) when using certain simple graph measures like neighborhood diversity, but it stays hard for more complex graph structures. Adding an upper cluster size limit helps make the problem easier for some graph types, but the problem remains tough otherwise. They also show limits on simplifications (kernelization) based on different parameters, and prove the problem is hard on graphs with limited complexity (bounded clique-width).
Network microaggregationStatistical disclosure controlFixed-parameter tractabilityNeighborhood diversityVertex coverTreewidthKernelizationW[1]-hardnessClique-widthGraph clustering
Authors
Ajinkya Gaikwad, Dušan Knop, Tomáš Valla
Abstract
Network microaggregation is a fundamental technique in statistical disclosure control, where vertices of a graph are partitioned into clusters satisfying size constraints and admitting a center within bounded distance. We study the parameterized complexity of the \emph{unweighted Connected Network Microaggregation} problem, focusing on structural parameters and natural clustering parameters such as the distance bound $d$ and cluster size gap $u-\ell$. We show that, unlike the weighted variant, the unweighted connected problem is fixed-parameter tractable when parameterized by neighborhood diversity, and hence by vertex cover. In contrast, it remains $\mathrm{W[1]}$-hard for more general structural parameters, including vertex deletion to paths, stars, and cliques. These hardness results hold even for every $d\ge 2$ and any fixed gap $u-\ell$, showing that these clustering parameters do not overcome the structural hardness. We further show that adding the cluster size bound $u$ restores tractability for structural parameters such as treewidth and cluster vertex deletion. Moreover, $u$ is essential: the problem remains $\mathrm{W[1]}$-hard when these structural parameters are considered alone. For kernelization, we prove that the problem has no polynomial kernel parameterized by vertex cover unless $\mathrm{coNP}\subseteq\mathrm{NP/poly}$, even when the distance constraint is vacuous. Adding $u$ yields a polynomial kernel for vertex cover, while kernelization remains unlikely for more general structural parameters even when combined with $u$. Finally, we show that the problem is NP-hard on graphs of bounded clique-width.