Parameterized Complexity of Fair Graph Clustering

Abstract

The problem of $\alpha-$ \textsl{BALANCED CLUSTER VERTEX DELETION} where \(\alpha \geq 1 \) is some constant, asks whether it is possible to delete at most \(k\) vertecies from a vertex colored graph such that that it becomes a cluster graph, where for each cluster, the ratios between the number of vertecies with each color is bounded by the constant \(\alpha \). We study the problem from a Parameterized Complexity point of view with the parameters \(k\) and \(l\), where \(k\) is the solution size and \(l\) is the number of colors. We present kernels with \(\mathcal{O}(k^2l)\) and \(\mathcal{O}(k^4) \) vertecies and an improved \(\mathcal{O}(k^3) \) kernel in the special case when \(\alpha = 1 \). We also provide an \(\mathcal{O}(3^k(|V|+|E|)) \) FTP algorithm.