Software Clustering Reframed

For thirty years, software clustering research has treated the modularization problem as an optimization problem: given a dependency graph, find the partition of elements that maximizes cohesion and minimizes coupling. Mitchell and Mancoridis established in 2006 that this problem is NP-complete. The field responded with metaheuristic search — hill-climbing, genetic algorithms, and weighted graph partitioning — each searching for structurally good partitions that, in the worst case, cannot be found exactly in polynomial time. This paper argues that the NP-hardness, while real, characterizes the difficulty of partitioning without a semantic criterion — not an inherent difficulty of modularization itself. The traditional clustering problem is hard because it operates without a semantic criterion: without knowing why elements change together, the optimizer cannot distinguish a well-motivated partition from a coincidental one. The result is exponential search over all possible groupings, with no basis for preferring one structurally plausible partition over another. The Independent Variation Principle (IVP) [1] provides a candidate criterion. Every element in a software system is governed by one or more change drivers — external conditions that, when they change, require the element to be modified. The change driver assignment Γ : 𝐸 →𝒫︀ (𝐶) maps each element to its set of governing drivers. The IVP partition 𝒫︀ Γ = 𝐸/ ∼Γ — obtained by grouping elements with identical driver assignments — is under the Change Management Hypothesis the modularization that minimizes both module-touch count per driver activation and within-module contamination cost. Given Γ, no search is needed: the partition is computed by a single pass over 𝐸 in time 𝑂(|𝐸| ⋅ 𝑑max log 𝑑max),where 𝑑max = max𝑒 |Γ(𝑒)| (simplifying to 𝑂(|𝐸|) when 𝑑max is bounded by a constant). The paper proves this polynomial-time result formally, shows that the traditional cohesion-coupling tension dissolves once a principled partitioning criterion is adopted, and locates the work’s contribution relative to Mitchell and Mancoridis, the Bunch tool, DSM methodology, and Maqbool and Babri’s survey. The hard part shifts from combinatorial search to driver identification — an inherently epistemic problem that domain analysis must address for principled modularization. The paper argues that the shift is an improvement: driver identification yields reusable knowledge; partition search yields a configuration that is discarded on every requirements change.