Fair Domination on Extended Supergrid Graphs: Complexity, Linear-Time Algorithms, and ILP Formulations

A dominating set of a graph is a subset of vertices such that every vertex is either contained in the set or adjacent to at least one vertex in it. A dominating set is called k-fair if each vertex not in this set is adjacent to exactly k vertices of the set. The domination and k-fair domination problems aim to find such sets of minimum cardinality. Both problems are NP-complete for general graphs, and the domination problem remains NP-complete on grid graphs, whereas the k-fair domination problem remains open on grid graphs. In this paper, we study the 1-fair and 2-fair domination problems on extended supergrid graphs, which generalize grid graphs and include both grid and supergrid graphs as subclasses. We prove that the 1-fair domination problem is NP-complete for these graph classes, even when restricted to planar graphs with maximum degree 4. On the positive side, for rectangular supergrid graphs, we present a linear-time algorithm for computing minimum 1-fair dominating sets. In addition, we formulate an integer linear programming (ILP) model to investigate the 1-fair and 2-fair dominations on small instances and introduce a restricted k-fair domination problem motivated by the experimental observations.