Conjunto Dominante Justo - Nascimento, Leonardo Valente; Pedrosa, Lehilton Lelis Chaves (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2025.8993, 2025)
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(3 tw ∆ 2tw+2 n) algorithm for general graphs, where ∆ is the maximum degree of the graph.