Watching Systems with Bounded Probes

Graph identification problems have been widely studied for their applications, ranging from fault diagnosis to network monitoring. A central issue in this domain is the identifying code, which seeks a subset of vertices whose neighborhoods uniquely identify every vertex in the graph. In this paper, we explore a generalization of this concept through watching systems, a more flexible identification framework that allows each vertex (watcher) to probe arbitrary subsets of its closed neighborhoods. We focus on a constrained variant called the β-Watching System problem, where each vertex can probe at most β subsets. This restriction models practical limitations in monitoring capacity and introduces new computational challenges. We formally define the β-Watching System problem, establish its relationship to classical identifying codes, and investigate its structural and algorithmic properties. Our main contributions include: new computational complexity for finding optimal β-watching systems; a (2 log n + 1)-approximation algorithm for general graphs; an exact polynomial-time algorithm for computing optimal β-watching systems on trees.