Dominating Set with Quotas: Balancing Coverage and Constraints

We study a natural generalization of the classical $\text{textsc}DominatingSet$ problem, called $\text{textsc}DominatingSetwithQuotas$ (DSQ). In this problem, we are given a graph $G$, an integer $k$, and for each vertex $v\in V(G)$, a lower quota ${\mathrm{l}\mathrm{o}}_v$ and an upper quota ${\mathrm{u}\mathrm{p}}_v$. The goal is to determine whether there exists a set $S\subseteq V(G)$ of size at most $k$ such that for every vertex $v\in V(G)$, the number of vertices in its closed neighborhood that belong to $S$, i.e., $\mathrm{\mid }N[v]\cap S\mathrm{\mid }$, lies within the range $[{\mathrm{l}\mathrm{o}}_v,{\mathrm{u}\mathrm{p}}_v]$. This richer model captures a variety of practical settings where both under- and over-coverage must be avoided – such as in fault-tolerant infrastructure, load-balanced facility placement, or constrained communication networks. While DS is already known to be computationally hard, we show that the added expressiveness of per-vertex quotas in DSQ introduces additional algorithmic challenges. In particular, we prove that DSQ becomes \W[1]-hard even on structurally sparse graphs – such as those with degeneracy 2, or excluding $K_{3,3}$ as a subgraph – despite these classes admitting FPT algorithms for DS. On the positive side, we show that DSQ is fixed-parameter tractable when parameterized by solution size and treewidth, and more generally, on nowhere dense graph classes. Furthermore, we design a subexponential-time algorithm for DSQ on apex-minor-free graphs using the bidimensionality framework. These results collectively offer a refined view of the algorithmic landscape of DSQ, revealing a sharp contrast with the classical DS problem and identifying the key structural properties that govern tractability.