Minimum $k$-Hop Dominating Sets in Grid Graphs

Given a graph $G$, the $k$-hop dominating set problem asks for a vertex subset $D_k$ such that every vertex of $G$ is in distance at most $k$ to some vertex in $D_k$ ($k\in \mathbb{N}$). For $k=1$, this corresponds to the classical dominating set problem in graphs. We study the $k$-hop dominating set problem in grid graphs (motivated by generalized guard sets in polyominoes). We show that the VC dimension of this problem is 3 in grid graphs without holes, and 4 in general grid graphs. Furthermore, we provide a reduction from planar monotone 3SAT, thereby showing that the problem is NP-complete even in thin grid graphs (i.e., grid graphs that do not a contain an induced $C_4$). Complementary, we present a linear-time $4$-approximation algorithm for $2$-thin grid graphs (which do not contain a $3\times 3$-grid subgraph) for all $k\in \mathbb{N}$.