Fair Dominating Set
Abstract
In the Dominating Set Problem (DS), given a graph G, the goal is to find a subset D ⊆ V of minimum size such that N [D] = V. We consider the β-Fair DS Problem (β-FDS), a variant of DS where V is the disjoint union of red and blue vertices, each vertex must be assigned to a dominating vertex in D, and the ratio between the number of vertices of each color assigned to an element of D must be at least β. This problem has applications in fair clustering, which aims to avoid group underrepresentation that is typically present in solutions produced by standard clustering algorithms. We show that β-FDS is W[1]-hard when parameterized by k + tw for each β > 0, where k is the size of the solution, and tw is the treewidth of the graph. For the special case where β = 1, we present an O(n∆) algorithm for trees and an O(3tw∆2tw+2n) algorithm for general graphs, where ∆ is the maximum degree of the graph.
References
Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms. Springer.
Dom, M., Lokshtanov, D., Saurabh, S., and Villanger, Y. (2008). Capacitated domination and covering: a parameterized perspective. In Proceedings of the 3rd International Conference on Parameterized and Exact Computation, IWPEC’08, page 78–90, Berlin, Heidelberg. Springer-Verlag.
Hochbaum, D. and Shmoys, D. (1985). A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10:180–184.
Palacios, J. L. (2008). On the simple symmetric random walk and its maximal function. The American Statistician, 62(2):138–140.
