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 + 1)-approximation algorithm for general graphs; an exact polynomial-time algorithm for computing optimal -watching systems on trees.
• Domination: ∀ ∈ , [] ∩ ̸= ∅ • Separation: ∀, ∈ with ̸= , [] ∩ ̸= [] ∩
Identifying codes have been extensively studied in a variety of settings. Depending on the type of
domination considered, the identification criteria applied, and the structural properties of the underlying
graphs, several variations of the identifying code problem have been proposed and investigated under
diferent names [
Watching systems have recently been introduced in [
A vertex ∈ is covered by a watcher = (, ) ∈ if ∈ ; the code () of is the set of watchers covering . The identifying condition requires that
() ̸= ∅ and () ̸= () for all ̸= .
We notice that an Identifying Code = {1, 2, . . . , ℓ} is a watching system with ℓ watchers (, []) for each ∈ . However, while it is well known that only twin-free graphs admit an
consider the trivial solution = {(1, {1}), . . . , (, {})}.
Moreover, as noticed in [
The first detailed analysis of watching systems was presented in [
We are interested in a constrained version of watching systems, where locations cannot be overloaded: a single vertex cannot be used as the location of a watcher for an indefinite number of times. Definition 4 ( -Watching System). For a watching system , define () = |{ ∈ | is ’s location}|. A -Watching System satisfies = max∈ () ≤ .
Of particular interest is the case = 1, called a single-location watching system (1-Watching System), where each vertex serves as a watcher location at most once. Given a 1-Watching System , to simplify the notation, the code of any vertex will be () = { | ∈ , (, ) ∈ }.
We study the following computational problem:
-Watching System ( -WS) 1A vertex is a twin of another vertex if [] = []. A graph is called twin-free if no vertex has a twin.
Input: A graph = (, ) and an integer .
Question: Does admit a -Watching System of size | | ≤ ? The corresponding optimization problem, Min -WS, seeks to find a -Watching System of minimum size.
This paper provides the first systematic study of the -Watching System problem. Our main contributions are threefold: • Strong complexity bounds for 1-Watching System: NP-hardness on bounded-degree graphs, exclusion of subexponential-time algorithms, and parameterized intractability (Section 2). • An (2 log + 1)-approximation algorithm for general -Watching System (Section 3). • An exact polynomial-time algorithm for -Watching System on trees (Section 4).
Auger et al. have shown that the Watching System problem is NP-hard [
Parameterized complexity is a refinement to classical complexity theory in which one takes into account
not only the input size, but also other aspects of the problem given by a parameter . A problem
with input size and parameter is called fixed parameter tractable (FPT) with respect to parameter ,
if it can be solved in time () · , where is a computable function only depending on and is a
constant. The inherent computational dificulty of solving many parameterized problems with even
small parameter values has suggested that certain parameterized problems are not fixed-parameter
tractable, which has motivated the theory of fixed-parameter intractability. The -hierarchy ⋃︀≥ 0 []
has been introduced to characterize the inherent level of intractability for parameterized problems
= [0] ⊆ [
A fpt-reduction from a parameterized problem to a parameterized problem ′ is an algorithm that transforms each instance ⟨, ⟩ of into an instance ⟨′, ()⟩ in time ()||(1), where and are computable functions, such that ⟨, ⟩ ∈ if and only if ⟨′, ()⟩ ∈ ′.
Flum, Grohe, and Weyer [
According to the ept-reduction, in [
We prove that 1-WS cannot be solved in time 2(), unless FPT= [
Proof. The proof is based on an ept-reduction from Dominating Set (DS). We recall that, given graph = (, ) and an integer , DS asks if there exists ⊆ such that || ≤ and ∩ () ̸= ∅ for each ∈ ∖ .
Starting from an instance ⟨, ⟩ of DS, the ept-reduction described below gives an instance ⟨′, ′⟩
of 1-WS in linear time and ′ = + ⌊log2 Δ⌋ + 1, where Δ is the maximum degree of any vertex in .
Since DS is [
We describe and analyze the desired ept-reduction. Let ⟨ = (, ), ⟩ be an instance of DS. Let Δ be the maximum degree of any vertex of and let 2− 1 ≤ Δ < 2 (i.e., = ⌊log2 Δ⌋ + 1). In the following, we assume that Δ ≥ 3 since when is a path or a cycle (i.e. Δ ≤ 2), the dominating set of can be immediately obtained. We construct a graph ′ = ( ′, ′) with | ′| = | | + + 2 − 1. Namely, ′ = ∪ ∪ where is a set of independent vertices and contains 2 − 1 independent vertices. The graph ′ = ( ′, ′) is then obtained starting from and connecting each vertex in the independent set with each vertex in the independent set , and connecting each vertex in to each vertex in . Formally, ′ = ∪ ∪ ,
′ = ∪ {(, ) | ∈ , ∈ } ∪ {(, ) | ∈ , ∈ }.
We show now that for any ⟨, ⟩ is a YES-instance of DS if ⟨′, ′ = + ⟩ is a YES-instance of 1-WS. (1) Assume first that is a dominating set of of size at most . W.l.o.g. we assume || ≥ 2. For any vertex ∈ ∖ choose any neighbor of in and denote it with . For each vertex ∈ , let () = { ∈ () ∖ | = }. Now, we define the desired watching system for ′. For each vertex ∈ , let = ∪ {} ∪ ().
Let = {1, 2, · · · , } and let = {1, 2, · · · , 2− 1}.
For each ∈ , – let () be the subset of consisting of all the vertices ∈ such that the value of bit in the binary representation of is 1; – for each ∈ , let () = {1, · · · , }. Define (, ), the subset of () consisting of all the vertices such that the value of bit in the binary representation of is 1 (recall ≤ Δ < 2). We set = {}∪()∪⋃︀∈ (, ). We claim that = {(, ) | ∈ }∪{(, ) | ∈ } is a 1-Watching System for . First of all, notice that | | = || + || ≤ + . By construction, each vertex in ′ has code () ̸= ∅. Indeed, () = ⎪⎪⎧{} ⎪ ⎪⎪⎪⎪{} ∪ ⎪ ⎪ ⎨{ ∈ | the value of bit in the binary
representation of is 1} ⎪ ⎪ ⎪ ⎪ ⎪⎪{} ∪ { ∈ | if = ∈ (), the value of bit ⎪ ⎪⎪⎩ in the binary representation of is 1} if ∈ ∖ . if ∈ , if ∈ , if = ∈ , (2)
Now we prove that for each pair of vertices , ′ in ′, it holds () ̸= (′). – , ′ ∈ . Let = and ′ = ′ . Since the binary representation of and ′ are diferent, we have () ̸= (′). – ∈ and ′ ∈ . Since ⊆ () and ∩ (′) = ∅, we have () ̸= (′). – , ′ ∈ . We have () ∖ = {} ̸= {′} = (′) ∖ . – ∈ and ′ ∈ . We have ∈ () and ∈/ (′). – ∈ and ′ ∈ ∖ . Since || ≥ 2, | () ∩ | ≥ 2 and | (′) ∩ | = |{′ }| = 1. – , ′ ∈ . () = {} ̸= {′} = (′). – ∈ and ′ ∈ . () ∩ ̸= ∅ and () ∩ = ∅ (recall (′) ⊂ ). – ∈ and ′ ∈ ∖ . (′) ∩ ̸= ∅ and () ∩ = ∅. – , ′ ∈ ∖. If ̸= ′ , then the claim holds since ∈ ()∖ (′) and ′ ∈ (′)∖ (). Otherwise, let and ′ be dominated by the same vertex ∈ (that is, , ′ ∈ ()). Let = and ′ = ′ with ̸= ′, and let be a bit in which and ′ difer. W.l.o.g., assume the value of bit in the binary representation of is 1. Hence, by (2) ∈ () ∖ (′), and the claim holds.
Let be a 1-Watching System for with | | ≤ + ; that is, locates at most + watchers each in a diferent vertex. We first claim that all the vertices in are locations of watchers to allow that the codes (), for ∈ , are non-empty and distinct. Assume that at most − vertices of , for ≥ 1, are locations of watchers. Let be the subset of vertices of that are not the location of watchers. In this case, at most 2− − 1 vertices in can have non-empty and distinct codes thanks to the watchers located in . Since the vertices in are the only neighbors of vertices in , and the vertices in are independent, we have that at least (2 − 1) − (2− − 1) ≥ (recall Δ ≥ 3 and then ≥ 2) vertices in need to be locations of watchers.
Hence, if watchers located in the vertices of are substituted with watchers located at the vertices in so that all the remaining vertices in have non-empty and distinct codes, we have that all the vertices in are locations of watchers. This implies that the 2 − 1 codes () for ∈ match with all the 2 − 1 non-empty subsets of the locations of watchers in .
By the above, we have that at most locations of watchers are in and that the codes (), (′) of any two vertices , ′ ∈ , must contain at least a vertex in that is a location of a watcher. Therefore, denoted by the set of locations in and considering that () ⊆ [] for each ∈ , we have () ∩ ̸= ∅ for each ∈ . Hence, is a dominating set of .
Corollary 1. 1-WS cannot be solved in time 2(), unless FPT= [
In this section, we prove the following result.
Theorem 2. Unless ETH fails, the 1-WS problem does not admit an algorithm working in time * (2(+)).
We present a linear reduction from 3-SAT to 1-WS.
Let be a 3-CNF boolean formula with variables 1, 2, · · · , and clauses 1, 2, · · · , where each clause is of length exactly three. We construct an instance ⟨, = 3 + 2⟩ of 1-WS. The graph is constructed as follows. – For each variable , with ∈ [], we introduce a variable gadget that is obtained by first considering a complete bipartite graph in which each of the two vertices in the independent set = {1, 2} is connected to each of the three vertices in the independent set = {1, 2, 3} and to the vertices corresponding to and ; and finally adding an edge connecting and . See Figure 1 on the left. – For each clause , with ∈ [], we introduce a clause gadget that is a complete bipartite graph in which each of the two independent vertices in the set = {1, 2} is connected to each of the three independent vertices in the set = {1, 2, 3} and to the vertex (resp. ) if (resp. ) appears in the clause . See Figure 1 on the right.
It is easy to see that the construction of can be done in linear time.
Claim 1. is satisfiable if
⟨, = 3 + 2⟩ is a YES-instance of 1-WS.
Proof. Let {1, 2, · · · , } be a satisfying assignment for , where corresponds to the truth value of the variable . We construct a 1-Watching System for () as follows: – For each ∈ [], if is true, then include the pair (, []) in , otherwise include (, []). – For each ∈ [], include the pairs (1, {1, 1, 2, , }),(2, {2, 2, 3}) in . – For each ∈ [], include the pairs (1, {1, 1, 2}), (2, {2, 2, 3}) in .
It is easy to see that the codes of the vertices of are the following and they are all distinct: (1) = {1}, (2) = {1, 2}, (3) = {2},
Ai xi
xi Xi xi xj Cq
Aq xk (1) = {1}, (2) = {1, 2}, (3) = {2}, (1) = {1} ∪ { | ∈ and is true} ∪ { | ∈ and is false}, (2) = {2} ∪ { | ∈ and is true} ∪ { | ∈ and is false}. Notice that the set { | ∈ and is true} ∪ { | ∈ and is false} ̸= ∅ since at least one of the literals in is true for each ∈ [].
Assume, now that is a solution for the instance ⟨, = 3 + 2⟩ of 1-WS.
If two watchers are used to have a diferent code for each vertex in (resp. ), then they are located at the two vertices of (resp. ). (Notice that if is such that three or more watchers are used to cover the vertices in some (resp. ), then we can rearrange such a solution by moving the location of two watchers to the vertices of (resp. ) and one watcher to one vertex in () ∖ (resp. () ∖ )). However, the two watchers in (resp. the two watchers in ) are able to generate at most three non-empty codes - one for each vertex in (resp. one for each vertex in )). Hence, at least a vertex in () ∖ and at least a vertex in () ∖ must be a location of a watcher (to be sure that each of the vertices in has a distinct code, and each of the vertices in has a distinct code). Since the total number of watchers in is 3 + 2, then there are watchers located in ︀( ⋃︀∈[] () ∖ )︀ ⋃︀ (︀ ⋃︀∈[] () ∖ )︀ . If there are at least 2 watchers located in () ∖ , then there are at least an ′ ∈ [] with ′ ̸= such that no watcher is in (′ ) ∖ ′ , and this is not possible. Hence, there is exactly 1 watcher located in () ∖ for each ∈ []; moreover, among these watchers at least one is also in () ∖ , for each ∈ []. This means that there is at least a literal, w.l.o.g. let say , in each clause , locating a watcher, i.e. ∈ () ∖ . Since ∈ () ∖ and at most one watcher is located in () ∖ , we have does not locate a watcher. Hence, giving value true to the literals whose vertices locate a watcher, we have a satisfying assignment for .
Since the reduction from 3-SAT is linear (that is, the output instance has size bounded by ( + )), if 1-WS admits an algorithm with running time 2(||), where is the size of the input instance, then composing the reduction with such an algorithm would yield an algorithm for 3-SAT running in time 2(+), which contradicts ETH, so completing the proof of Theorem 2.
It is easy to see that the lower bound given in Theorem 2 is tight. Indeed, given an instance ⟨, ⟩ of 1-WS, we could try each subset of (), with || ≤ , to locate watchers and then, removing all the edges in () that are not incident on , so obtaining a set of edges , we could try each subset of edges in to identify the subset of neighbors for each vertex ∈ , i.e., = { | ∈ [], (, ) ∈ }. Finally, we check if = {(, ) | ∈ } is a watching system of .
We prove now that 1-WS remains NP-hard even when the degree of the input graph is bounded. We
establish the hardness by a reduction from the variant of 3-SAT in which each clause is of length exactly
3 and each variable occurs exactly twice unnegated and twice negated. This variant was shown to be
NP-complete by Darmann and Döcker in [
Consider any 3-CNF boolean formula with variables 1, 2, · · · , and clauses 1, 2, · · · , such that each clause is of length exactly three, and each variable appears twice unnegated and twice negated, and use the same construction given in Theorem 3. The vertices in the sets , in gadget for all ∈ [] have degree at most five and the vertices in the sets , in gadget , for ∈ [], have degree at most six. Furthermore, since each literal appears in exactly 2 clauses, it is easy to see that the maximum degree of is seven. Also, the construction of can be done in linear time.
Following the proof of Theorem 3, we can prove that is satisfiable if ⟨, = 3 + 2⟩ is a YES-instance of 1-WS. Hence, we have the theorem.
Theorem 3. 1-WS is NP-hard even on graphs with maximum degree seven.
problem Before describing the algorithm, we make the following observation: Given a watching set for a graph , if all vertex codes are distinct but a vertex has the empty code ( () = ∅), we can easily construct a watching system by adding an extra watcher = (, {}). For the sake of simplicity, in this section, we allow the presence of empty codes, as resolving them requires adding at most one additional watcher, thus increasing the size of the watching system by at most one.
For a graph = (, ), let the set of all the possible -Watching System, we define a function : → N, as follow:
Consider a watching set = {1, 2, . . . , } ∈ where each is a couple = (, ), is a vertex and ⊆ []. We denote by ( ) = { ∈ | () = ()} the set that comprises all the vertices having the same code of according to the watching set .
We denote by ( ) = |( )| the cardinality of ( ), that is, the number of times the code associated with vertex is repeated across all vertices in the graph. Analogously, for each code ℓ ∈ 2 we denote by ℓ( ) = |{ ∈ | () = ℓ}| the number of times the code ℓ is repeated across all vertices in the graph.
For any possible set of watchers let ( ) = 2 − ∑︁ ( ) ∈ (3)
We notice that ∑︁ ( ) = ∑︁ ℓ( )2, that is, the sum of the squares of the multiplicities of each code.
∈
ℓ∈2 Lemma 1. The following properties of hold: (i) is integer valued; (ii) (∅) = 0; (iii) is non-decreasing; (iv) For every watching set ∈ , ( ) ≤ 2 − . Moreover, ( ) = 2 − if and only if all codes are distinct.
Proof. (i) trivially hold by definition of .
To prove (ii), we notice that if = ∅, then the same code (the empty one) is shared by all the vertices and, consequently, (∅) = 2 − 2 = 0.
To prove (iii), it sufices to show that for each ∈ and for each watching set and each watcher ∈/ , we have ( ∩ {}) ⊆ ( ) and consequently the function () is non-increasing. Indeed, each time we add a new watcher = (, ) ∈/ , we have that if ∅ ̸= ∩ ( ) ⊂ ( ) then ( ∪ {}) ⊂ ( ). Otherwise ( ∪ {}) = ( ).
Consider now (iv). Let be a watching set. Since every vertex receives a code, we have ∑︀∈ ( ) ≥ and thus 2 − is the maximum value of the function .
The maximum value ( ) = 2 − is achieved if and only if each vertex has a unique code—i.e., all codes are distinct. For example, the trivial watching set = {(1, {1}), . . . , (, {})} ∈ assigns a distinct code to each vertex, achieving () = 2 − .
Conversely, if at least one code is repeated, then there exist at least two vertices sharing the same code. In that case, ∑︀∈ ( ) ≥ ( − 2) + 2 + 2 and consequently ( ) < 2 − . Lemma 2. The function , given in (3), is submodular.
Proof. Recall that a function : → is submodular if for all 1, 2 ∈ with 1 ⊆ 2 and for all ∈/ 2, the inequality (2 ∪ {}) − (2) ≤ (1 ∪ {}) − (1) holds.
Recalling that the class of submodular functions is closed under non-negative linear combinations, it sufices to show that, for each ∈ , the function − ( ) is submodular, that is. That is, we need to verify the inequality: (2) − (2 ∪ {}) ≤ (1) − (1 ∪ {}). (4) for all 1, 2 ∈ with 1 ⊆ 2 and ∈/ 2.
To prove this, consider a watching set , a watcher = (, ) ∈/ and any vertex . There are two cases to consider, depending on the relation between and .
Assume first that ∈/ . In this case, we have:
Hence, or equivalently
( ∪ {}) = ( ) ∖ . ( ∪ {}) = ( ) − | ∩ ( )|, ( ) − ( ∪ {}) = | ∩ ( )|.
Using this relation on both sides of inequality (4), we obtain:
| ∩ (2)| ≤ | ∩ (1)|.
Noting that (2) ⊆ (1) (see proof of (iii) above), we have that the inequality (4) holds.
The case ∈ is proved with the same arguments, using = ∖ in place of .
Theorem 4. min- -WS can be approximated in polynomial time by a factor of 2 log + 1.
Proof. Let denote the natural greedy strategy which starts with = ∅ and iteratively adds to
the element ∈/ that maximizes the marginal gain ( ∪ {}) − ({}), until ( ) = 2 − is
achieved. By a classical result of Wolsey [
({}) ≤ 2 − (2/4 + 2/4) = 2/2.
Hence the approximation provided by the algorithm is
ln(2/2) + 1 < log(2/2) + 1 = 2 log .
Additionally, since the final solution may still include a vertex associated with the empty code, we may need to add one extra watcher to obtain a watching system. This increases the approximation ratio by at most 1, yielding a final approximation factor of 2 log + 1.
It is worth mentioning that, to identify the watcher that maximizes the marginal gain at each step, the algorithm considers all the vertices ∈ as the location of a new watcher , excluding those that have already been used times. For each candidate location , the maximal marginal gain can be computed in polynomial time based on the following observations: • Assigning the new code ℓ′ = ℓ ∪ {} to a vertex having code ℓ does not afect the value of the function for all the vertices having a diferent code. Therefore, the vertices can be grouped by their current codes, and each group can be analyzed independently. • Within a group of vertices sharing the same code ℓ, updating any subset of them to receive the new code ℓ′ = ℓ ∪ {}, has the same efect on , regardless of which specific vertices are chosen. As a result, it is suficient to determine, for each group, how many vertices should be updated, rather than which ones.
Hence, once the location of the watcher is fixed, the optimal subset ⊆ [] that maximizes the marginal gain can be computed as follows. For each code ℓ appearing among the vertices in [], define: • = |{ ∈ [] | () = ℓ}| : the number of vertices in [] with code ℓ, • = |{ ∈ | () = ℓ}| : the total number of vertices in the graph with code ℓ. The objective is to choose a value 1 ≤ ≤ , representing how many vertices in the group should have their code updated from ℓ to ℓ′ = ℓ ∪ {}, in a way that maximizes the increase in . Since maximizing the increase in corresponds to minimizing the function () = 2 + ( − ), which is convex and minimized at = /2, the optimal number of updates is = min{, ⌊/2⌋}.
Thus, for a fixed location , an optimal subset ⊆ [] can be computed in (| []|) time. Since this procedure is repeated for each candidate vertex , the overall time complexity for identifying the locally optimal watcher at each step is ().
In this section, given a watching set , with a slight abuse of notation, we refer to a vertex as a watcher if is the location of at least one watcher in .
We give a dynamic programming algorithm, which, exploiting the structure of the input graph (a tree), enables us to solve the min- -WS problem.
Before proceeding with the description of the algorithm, the following observation should be noted. Observation 1. Given a graph = (, ) and a watching set . If a node is covered by at least two watchers in , then its code () is unique.
Given a tree = (, ), we root it at an arbitrary vertex , and define () as the subtree of vertex , for any ∈ . We denote by ( ()) the vertex set of (). Moreover, for each ̸= , we denote by () the parent of and by ℎ() the set of children of in .
The algorithm processes the vertices in a postorder manner, so that all children’s vertices are always visited before their parent.
Fix a vertex ∈ and consider the tree (). In order to be able to recursively reconstruct the solution, the algorithm calculates partial solutions associated with (), under diferent hypotheses, based on the following considerations.
The vertex can be either a watcher (cases , , ) or not (cases , , ). If is a watcher, then it is necessary to distinguish three cases: (a) The watching set , associated with (), is a watching system for the nodes in ( ()) plus the parent node () (that is, it enables to identify all the nodes in ( ()) ∪ {()}); (b) The watching set , associated with (), is a watching system for the nodes in ( ()); (c) The watching set , associated with (), is a watching system for the nodes in ( ()) ∖ {}.
In the case is not a watcher, it is necessary to distinguish three additional cases: (d) The watching set , associated with (), is a watching system for the nodes in ( ()); (e) The watching set , associated with (), is a watching system for the nodes in ( ()) ∖ {} and at least one child of is a watcher; (f) The watching set , associated with (), is a watching system for the nodes in ( ()) ∖ {}.
Hence, the following cases are considered: Case: is a watcher: We consider three sub-cases:
Case : The watching set , associated with (), satisfies the inequality ∙ log(′() + 3) ≤ () ≤ , if no children of is a watcher ∙ log(′() + 2) ≤ () ≤ , if at least one children of is a watcher where ′() denotes the number of children of that have only a single watcher in their neighborhood—namely, itself.
According to Observation 1, only the children that have a single watcher require distinct codes, provided by , since no other watcher helps distinguish them. The additional 3 codes account for the following: the empty code is not permitted, one code must be assigned to itself (this is not needed if at least one child of is a watcher), and one code may be reserved for the parent (), in case it is needed. That is, the watching set , associated with (), is a watching system for the nodes in ( ()) plus the parent node ().
Case : The watching set , associated with (), satisfies the inequality ∙ log(′() + 2) ≤ () ≤ , if no children of are watcher ∙ log(′() + 1) ≤ () ≤ , if at least one children of is a watcher ∙ log(′() + 1) ≤ () ≤ , meaning it is a watching system for the nodes in ( ()).
Case : The watching set , associated with (), satisfies the inequality
meaning it is a watching system for the nodes in ( ()) ∖ {}.
We notice that if at least one child of is a watcher, cases and coincide.
Case is not a watcher: We consider three sub-cases:
Case : The watching set , associated with (), is a watching system for the nodes in ( ()). This occurs when has at least two watchers among its children, or one child can provide an additional distinct code (see Case ).
Case : The watching set , associated with (), is not a watching system in ( ()), and there exists a child ∈ ℎ() such that is a watcher (i.e., is covered by one watcher).
Case : The watching set , associated with (), is not a watching system in ( ()).
We notice that for cases , , we have that all the vertices in () have a distinct code, and consequently, they enable us to identify a -Watching System. The other cases are auxiliary and will be used to reconstruct the solutions related to the tree, rooted in , starting from the solutions of the trees rooted in each of its children.
Definition 5. Let = (, ) be a tree of vertices. For each ∈ , we denote by [, ] the size of an optimal partial solution * , such that all the vertices in ( ()) ∖ {} have a distinct code and case ∈ {, , , , , } occurs.
According to Definition 5, the size of an optimal -Watching System for is
We compute all the values [, ], for ∈ {, , , , , } and for each ∈ , using a bottom up approach. In particular, for each leaf ℓ we have, min{[, ], [, ], [, ]}. [ℓ, ] = {︃2 ∞ if ≥ 2
Othewise, [ℓ, ] = [ℓ, ] = 1, [ℓ, ] = [ℓ, ] = ∞,
[ℓ, ] = 0.
For each internal vertex , we consider first the cases where is a watcher.
Let the number of children of , we denote the ℎ children of . We are going to build another auxiliary table to compute the optimal solution of internal nodes.
Definition 6. Let = (, ) be a tree of vertices. For each ∈ , and 1 ≤ ≤ ≤ , we denote by • [, , , 0] the size of an optimal partial solution for the forest (1), (2), . . . , () such that at most vertices among 1, 2, . . . , are not covered by any watcher while none of them is a watcher. • [, , , ≥ 1] the size of an optimal partial solution for the forest (1), (2), . . . , () such that at most vertices among 1, 2, . . . , are not covered by any watcher and there is at least one watcher among the vertices 1, 2, . . . , .
We denote by [, , ] = min{ [, , , 0], [, , , ≥ 1]} the size of an optimal partial solution for the forest (1), (2), . . . , () such that at most vertices among 1, 2, . . . , are not covered by any watcher.
We have [, 1, , 0] = {︃min∈{,}{[1, ]}
if = 0 min∈{,,}{[1, ]} if = 1 For all 1 < ≤ ,
⎧ [, − 1, − 1, 0] + min∈{,,}{[ , ]} [, , , 0] = ⎪⎨ {︃ ⎪min ⎩ [, − 1, , 0] + min∈{,}{[ , ]} [, − 1, − 1, 0] + [ , ] For the table [· , · , · , ≥ 1], we have [, 1, , ≥ 1] = ∈m{i,n,}{[1, ]} for = 0, 1. Exploiting the table , we are able to compute the values for . We have, [, ] = min [, ] = min {︃min0≤ ≤ { [, , , 0] + ⌈log( + 3)⌉}, where ≤ and ⌈log( + 3)⌉ ≤
min0≤ ≤ { [, , , ≥ 1] + ⌈log( + 2)⌉}, where ≤ and ⌈log( + 2)⌉ ≤ {︃min0≤ ≤ { [, , , 0] + ⌈log( + 2)⌉}, where ≤ and ⌈log( + 2)⌉ ≤ min0≤ ≤ { [, , , ≥ 1] + ⌈log( + 1)⌉}, where ≤ and ⌈log( + 1)⌉ ≤ [, ] = min { [, , ] + ⌈log( + 1)⌉}, where ≤ and ⌈log( + 1)⌉ ≤
0≤ ≤
We notice that [, ] ≥ [, ] ≥ [, ]. From now on, we consider cases where is not a watcher. We have, [, ] = min {︃min1,2∈ℎ(){[1, ] + [2, ] + ∑︀∈ℎ()∖{1,2} min∈{,} [, ]} min∈ℎ(){[, ] + ∑︀∈ℎ()∖{} min∈{,} [, ]} (5) (6) (7) (8) (9) (10) [, ] =
⎧ min ⎨ ∈ℎ() ⎩ [, ] = [, ] +
∑︁ ∈ℎ()
∑︁ ∈ℎ()∖{} [, ].
[, ] ⎫ ⎬ ⎭ Theorem 5. Let = (, ) be a tree of vertices. We can compute a solution for the instance ⟨, ⟩ of the min- -WS problem in time (Δ3), where Δ is the maximum degree of any vertex in . Proof. By induction on the tree, we can prove that the recursive formula presented in (5)–(10) coincides with the definition of [· , · ]; hence, the algorithm described above is correct.
time (Δ2). Given the table [, · , · , · ], the computation of [, · ] comprises (1) values, which can be computed in time (Δ). Hence, the optimal value, which corresponds to
min{[, ], [, ], [, ]} can be computed within (Δ3) time. An optimal watching system * can be computed within the same time by a standard backtracking technique.
The authors have not employed any Generative AI tools.