Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity
This addresses fairness in clustering algorithms, providing theoretical insights for researchers in computational complexity and fair machine learning, though it is incremental as it builds on known hardness results.
The paper tackles the problem of fair means clustering of discrete vectors, showing it is NP-hard and lacks fixed-parameter tractability in the fair setting, but identifies conditions for tractability such as constraints, approximations, or alternative parameterizations.
We study the computational problem of computing a fair means clustering of discrete vectors, which admits an equivalent formulation as editing a colored matrix into one with few distinct color-balanced rows by changing at most $k$ values. While NP-hard in both the fairness-oblivious and the fair settings, the problem is well-known to admit a fixed-parameter algorithm in the former ``vanilla'' setting. As our first contribution, we exclude an analogous algorithm even for highly restricted fair means clustering instances. We then proceed to obtain a full complexity landscape of the problem, and establish tractability results which capture three means of circumventing our obtained lower bound: placing additional constraints on the problem instances, fixed-parameter approximation, or using an alternative parameterization targeting tree-like matrices.