PaperlayerView exact revision on arXiv

Source-linked AI summary

Parameterized Complexity of Connected Network Microaggregation: The Role of Cluster Size

Ajinkya Gaikwad, Dušan Knop, Tomáš Valla

arXiv:2608.28920v1cs.DS

TL;DR

Connected Network Microaggregation must balance privacy-preserving clustering with connectivity, while the role of the upper cluster-size bound in parameterized complexity is unclear. The paper analyzes structural and clustering parameters, finding that u restores tractability in several settings but structural parameters alone often do not.

  • Problem

    Connected microaggregation requires connected clusters with bounded sizes and distances, and the upper bound u is crucial because connectivity prevents arbitrarily splitting clusters.

  • Method

    The paper studies fixed-parameter tractability, hardness, and kernelization for unweighted Connected Network Microaggregation under structural parameters and clustering parameters including d, u, and ℓ.

  • Results

    The problem is FPT by neighborhood diversity and vertex cover, becomes tractable with u for treewidth and cluster vertex deletion, but remains W[1]-hard or lacks polynomial kernels under several structural parameterizations alone or with u.

  • Takeaways & Limitations

    The results establish a dichotomy in which combining structural parameters with u can yield tractability or kernels, whereas structural parameters alone are insufficient in several settings.

  • Takeaways & Limitations

    Whether polynomial kernels exist for twin-cover or neighborhood diversity combined with u remains open, alongside other unresolved complexity cases.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies unweighted Connected Network Microaggregation and maps when structural and clustering parameters yield tractability, hardness, or efficient preprocessing. Its central finding is that the upper cluster-size bound u restores tractability in several settings, whereas d and u−ℓ do not overcome structural hardness.

  • Problem setting: Network Microaggregation partitions graph vertices into size-constrained clusters with bounded-distance centers; the connected variant additionally requires each cluster to induce a connected subgraph.Centers need not belong to their clusters, and one vertex may center multiple clusters.
  • Research focus: The paper focuses on the unweighted connected variant and systematically tests structural parameters combined with d, u, and slack u −ℓ.The goal is to identify combinations that provide fixed-parameter tractability or efficient preprocessing.
  • Positive results: Neighborhood diversity yields fixed-parameter tractability, and consequently vertex cover does as well, for unweighted Connected Network Microaggregation.
  • Hardness results: Vertex deletion to paths, stars, or cliques remains W[1]-hard even for all d ≥2 and any fixed u −ℓ, so these clustering parameters do not remove structural hardness.
  • Positive results: Adding u gives fixed-parameter tractability for treewidth and for cluster vertex deletion, while cluster vertex deletion alone remains W[1]-hard.The combination of cluster vertex deletion and the maximum clique size is also FPT when d ≥3.
  • Kernelization and classical hardness: Vertex cover plus u admits a polynomial kernel, but polynomial kernels remain unlikely for vertex deletion to stars or paths even with u; bounded-clique-width instances remain NP-hard.The kernel lower bounds hold even when d ≥u, and the clique-width hardness holds in particular for clique-width at most 4.

2 Preliminaries

This section defines the graph, clustering, and structural-parameter terminology used for Connected Network Microaggregation. The problem asks whether vertices can be partitioned into connected clusters satisfying size and center-distance constraints.

  • Graph and clustering notation: The paper works with simple undirected graphs G=(V,E), using N(v) for open neighborhoods, induced subgraphs G[S], and graph distances dist_G(u,v).
  • Graph and clustering notation: A connected clustering is a partition of V into clusters, each inducing a connected subgraph and having an associated center vertex.Centers may be outside their clusters and may be reused across clusters.
  • Structural parameters: Neighborhood diversity partitions vertices into type classes whose members have the same neighborhood type, meaning they are true or false twins.
  • Structural parameters: Treewidth and pathwidth are defined through minimum-width tree and path decompositions, while cluster vertex deletion measures deletion to a disjoint union of complete graphs.
  • Structural parameters: Clique-width is the minimum number of labels needed to construct a graph using vertex creation, disjoint union, label joining, and relabeling operations.
  • Problem definition: CNMA asks whether V has a partition into clusters of sizes between ℓ and u such that every cluster is connected and every vertex lies within distance d of its center.

3 Fixed Parameter Tractability and Kernelization

The section establishes tractability results for Connected Network Microaggregation under neighborhood diversity, vertex cover, treewidth, and cluster vertex deletion, together with a polynomial kernel for vertex cover plus u. It also gives an ILP-based neighborhood-diversity algorithm, dynamic programming for treewidth plus u, and an FPT result for cluster vertex deletion plus clique size when d ≥3.

  • Neighborhood diversity and ILP: Connected Network Microaggregation is FPT when parameterized by neighborhood diversity, and consequently when parameterized by vertex deletion to clique.The proof partitions vertices into neighborhood types and formulates feasible cluster supports and centers through an integer linear program.
  • Kernelization: Connected Network Microaggregation admits a polynomial kernel of size vc · u when parameterized by vc + u.If ℓ > 1, every connected cluster contains a vertex-cover vertex, so more than ku vertices immediately yields a no-instance; ℓ = 1 is handled separately as trivial.
  • Treewidth: Connected Network Microaggregation is FPT when parameterized by treewidth plus u.For d > u, the running time is (u(w + 1)^2)^(2(w+1)) · n^O(1), while d ≤ u is covered by a known treewidth-plus-d-plus-u algorithm.
  • Cluster vertex deletion: Connected Network Microaggregation is FPT when parameterized by cluster vertex deletion number plus u.The section also gives an FPT algorithm parameterized by cluster vertex deletion number plus maximum clique size for every d ≥3.
  • Cluster vertex deletion: The cluster vertex deletion plus maximum-clique-size result requires d ≥3 because the center-equivalence argument fails for d = 2.For d = 2, vertices can agree on their neighborhoods and two-step neighborhoods in the deletion set while having different distance-2 behavior.

4 Lower bounds on Kernelization

The paper establishes broad polynomial-kernel lower bounds for Connected Network Microaggregation through parameterized reductions from Red-Blue Dominating Set. These lower bounds persist for vertex cover, vertex deletion to cliques, and several broader structural classes, even with restrictive or vacuous distance and size settings.

  • Unless coNP ⊆ NP/poly, no polynomial kernel exists under vertex cover, even for all d ≥3.
  • The vertex-cover lower bound uses a polynomial parameter transformation from Red-Blue Dominating Set, with gadget constructions encoding domination through connected clusters.The constructed instances have vertex-cover size polynomially bounded in the source parameter, and feasibility is equivalent in both directions.
  • Unless coNP ⊆ NP/poly, no polynomial kernel exists for vertex deletion distance to a clique, even when d = 3.The reduction forces one cluster to contain exactly k red vertices, which must dominate all blue vertices.
  • For graph classes containing connected graphs of every size with a pendant vertex, kernelization remains unlikely under vertex deletion distance to the class plus u, even for all d ≥u.The construction preserves equivalence while polynomially bounding the combined parameter.
  • The same lower-bound framework yields no polynomial kernel for vertex integrity plus u, and for deletion to paths or stars plus u.The vertex-integrity construction bounds the combined parameter by 3(|B|+k+1).

5 W[1]-hardness Results

The paper proves robust W[1]-hardness for Connected Network Microaggregation under many structural parameters, even when d ≥2 and the gap u−ℓ is fixed. It also derives NP-hardness for bounded clique-width and feedback-edge-set hardness.

  • The hardness holds even when d ≥2 and u−ℓ = r for any fixed r ≥0.Thus, permissive distance bounds and fixed cluster-size gaps do not remove the structural hardness.
  • The reduction builds anchor gadgets and connected item gadgets so that every feasible cluster contains exactly one anchor and items totaling the bin capacity B.The size inequalities force each cluster to represent one valid Unary Bin Packing bin.
  • Connected Network Microaggregation is NP-hard on graphs of clique-width at most 4, even when d ≥2 and u−ℓ = r.The construction uses only four labels.
  • For every fixed r ≥0, the problem is W[1]-hard under deletion distance to paths, stars, cluster vertex deletion, feedback vertex set, treedepth, pathwidth, and treewidth.These results follow from a parameterized reduction from Unary Bin Packing.
  • A parameter-preserving reduction from Equitable Connected Partition implies W[1]-hardness for feedback edge set.The reduction keeps the graph unchanged and sets d := n and ℓ = u := n/r.

6 Conclusion

The conclusion presents a dichotomy: adding the upper cluster-size bound u to structural parameters yields tractability and, for vertex cover, polynomial kernels, whereas structural parameters alone remain insufficient. The paper leaves combined-kernelization cases and approximation directions open.

  • Combining structural parameters with u yields fixed-parameter tractability, and vertex cover plus u additionally admits polynomial kernels.
  • Structural parameters alone remain insufficient because the problem is W[1]-hard and lacks polynomial kernels under several parameterizations.
  • Hardness persists even under d = 1 and ℓ = u, so tight distance bounds and exact cluster sizes do not simplify the problem.
  • Open directions include polynomial kernels for twin-cover or neighborhood diversity combined with u, approximation algorithms, and unresolved complexity cases.
Loading 2608.28920v1…