Dominating Set with Quotas: Balancing Coverage and Constraints
2026-04-06 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a new version of a classic graph problem called Dominating Set, adding rules that each node must be covered by a specific number of nearby chosen nodes, not too few or too many. They show this makes the problem harder, even on simple types of graphs where the original problem was easier. However, they also identify certain graph types and parameters where this tougher problem can still be solved efficiently. Their work highlights how adding coverage limits changes the computational complexity and which structures help make the problem manageable.
Dominating SetGraph TheoryParameterized ComplexityW[1]-hardnessFixed-Parameter Tractable (FPT)TreewidthNowhere Dense GraphsBidimensionalityApex-Minor-Free GraphsDegeneracy
Authors
Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh, Sanjay Seetharaman, Anannya Upasana
Abstract
We study a natural generalization of the classical \textsc{Dominating Set} problem, called \textsc{Dominating Set with Quotas} (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{lo}_v \) and an upper quota \( \mathrm{up}_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., \( |N[v] \cap S| \), lies within the range \( [\mathrm{lo}_v, \mathrm{up}_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.