The Berlin Safe House Puzzle: Spycraft via Interval Graphs

Since $I_a\prec I_b$ and $I_a\cap I_b\ne \mathrm{\varnothing }$, by (1) we have $\mathrm{\ell }(I_b)\le r(I_a)$. Furthermore, for each $I_c$ with $a\le c\le b$, it holds $r(I_a)\le r(I_c)\le r(I_b)$. Hence, $\mathrm{\ell }(I_b)\le r(I_c)\le r(I_b)$, implying $I_c\cap I_b\ne \mathrm{\varnothing }$. $◀$

The following lemma states that if a given set of bugs forms a Partial Surveillance System, then one can identify the signatures that certify this property by exploiting the lexicographic order on bug signatures.

By hypothesis, $B$ is a PSS for ${ℐ}_i$. Hence, at least a list of signature ${𝒮}^{\prime }=(S_1^{\prime },\mathrm{\dots },S_i^{\prime })$ satisfying (4) exists. In the following, we transform ${𝒮}^{\prime }$ to match $𝒮$. We proceed by induction on $i$.

If $S_1^{\prime }=S_1$, then there is nothing to prove. If the signature $S_1$ does not appear in ${𝒮}^{\prime }$, then it is sufficient to set $S_1^{\prime }=S_1$.

Otherwise, $S_1$ appears in ${𝒮}^{\prime }$ as the signature of some interval $I_p$ with $p>1$, i.e., $S_p^{\prime }=S_1$. We show that the signatures of $I_1$ and $I_p$ can be swapped in ${𝒮}^{\prime }$ that is $S_p^{\prime }\subseteq {\mathrm{\Sigma }}_1$ and $S_1^{\prime }\subseteq {\mathrm{\Sigma }}_p$, so that ${𝒮}^{\prime }$ and $𝒮$ agree on $I_1$.

Since $S_p^{\prime }=S_1\subseteq {\mathrm{\Sigma }}_1$, it remains to prove that $S_1^{\prime }\subseteq {\mathrm{\Sigma }}_p$. Suppose, for contradiction, that the signature $S_1^{\prime }⊈{\mathrm{\Sigma }}_p$. This implies that there exists a bug $z\in S_1^{\prime }$ with $z\notin {\mathrm{\Sigma }}_p$. Let $z$ be located in $I_h$, we have $I_h\cap I_p=\mathrm{\varnothing }$.

Because $S_1$ is the first signature in the construction of $𝒮$, we know $S_1=\{b\}$, where bug $b$ is the first bug in ${\mathrm{\Sigma }}_1$ (according to (2)). Let bug $b$ be located in the interval $I_q$ with $q\ge 1$.

We know that:

• $\mathrm{■}$

  $S_p^{\prime }=S_1=\{b\}$ implies that bug $b\in {\mathrm{\Sigma }}_p$ and, consequently,

  $$I_q\cap I_p\ne \mathrm{\varnothing }$$

• $\mathrm{■}$

  $z\in S_1^{\prime }$, and consequently $z\in {\mathrm{\Sigma }}_1$. Moreover, $S_1=\{b\}$, and $S_1$ is the first signature in lexicographic orderon ${\mathrm{\Sigma }}_1$. It follows that and by (2) consequently

  $$q\le h.$$

We distinguish two cases:

Recalling that $z\in {\mathrm{\Sigma }}_1$ and $z$ is located in $I_h$, we have $I_1\cap I_h\ne \mathrm{\varnothing }$. Using $p\le h$ and $I_1\cap I_h\ne \mathrm{\varnothing }$, we know by Fact 7 that $I_p$ must also intersect $I_h$, which contradicts $I_h\cap I_p=\mathrm{\varnothing }$.

Using and $I_q\cap I_p\ne \mathrm{\varnothing }$, we know by Fact 7 that $I_h$ must also intersect $I_p,$ which contradicts $I_h\cap I_p=\mathrm{\varnothing }$.

Thus, the contradiction shows that the signature $S_1^{\prime }$ can be assigned to $I_p$ and the swap is feasible.

Assume that lists ${𝒮}^{\prime }$ and $𝒮$ agree on their first $i-1$ entries. Since ${\mathrm{\Sigma }}_i$ depends only on the bug placement and both the lists ${𝒮}^{\prime }$ and $𝒮$ agree on their first $i-1$ entries, both $S_i^{\prime }$ and $S_i$ belong to the same set that is the set of all the subsets of ${\mathrm{\Sigma }}_i$ excluding $\{S_1,\mathrm{\dots },S_{i-1}\}.$ This set is nonempty because ${𝒮}^{\prime }$ satisfies (4).

If $S_i^{\prime }=S_i$, or if $S_i$ does not appear in ${𝒮}^{\prime }$, we are done. Otherwise, $S_i$ appears in ${𝒮}^{\prime }$ as the signature of some interval $I_p$ with $p>i$, i.e., $S_p^{\prime }=S_i$.

We show that the signatures of $I_i$ and $I_p$ can be swapped in ${𝒮}^{\prime }$ that is $S_p^{\prime }\subseteq {\mathrm{\Sigma }}_i$ and $S_i^{\prime }\subseteq {\mathrm{\Sigma }}_p$, obtaining that ${𝒮}^{\prime }$ and $𝒮$ agree on their first $i$ entries.

Since $S_p^{\prime }=S_i\subseteq {\mathrm{\Sigma }}_i$, it remains to prove that $S_i^{\prime }\subseteq {\mathrm{\Sigma }}_p$. Suppose, for contradiction, that the signature $S_i^{\prime }⊈{\mathrm{\Sigma }}_p$. This implies that there exists a bug $z\in S_i^{\prime }$ with $z\notin {\mathrm{\Sigma }}_p$. Let $z$ be located in $I_h$, we have $I_h\cap I_p=\mathrm{\varnothing }$.

Let $b$ be the first bug (under (2)) in the signature $S_i$ and let it be located in interval $I_q$.

We know that:

• $\mathrm{■}$

  Since $b\in S_i=S_p^{\prime },$ we have that bug $b\in {\mathrm{\Sigma }}_p$ and consequently

  $$I_q\cap I_p\ne \mathrm{\varnothing }$$

• $\mathrm{■}$

  $z\in S_i^{\prime }$, and consequently $z\in {\mathrm{\Sigma }}_i$. Moreover, $b\in S_i$, and $S_i$ is the first signature in lexicographic order taken from the set of all the subsets of ${\mathrm{\Sigma }}_i$ excluding $\{S_1,\mathrm{\dots },S_{i-1}\}$. It follows that and by (2) consequently

  $$q\le h.$$

We distinguish two cases:

Recalling that $z\in {\mathrm{\Sigma }}_i$ and $z$ is located in $I_h$, we have $I_i\cap I_h\ne \mathrm{\varnothing }$. Using and $I_i\cap I_h\ne \mathrm{\varnothing }$, we know by Fact 7 that $I_p$ must also intersect $I_h$, which contradicts $I_h\cap I_p=\mathrm{\varnothing }$.

Using and $I_q\cap I_p\ne \mathrm{\varnothing }$, we know by Fact 7 that $I_h$ must also intersect $I_p,$ which contradicts $I_h\cap I_p=\mathrm{\varnothing }$.

The contradiction shows that the signature $S_i^{\prime }$ can be assigned to $I_p$, and the swap is feasible. $◀$

Exploiting the result of Lemma 8, the algorithm ComputeSignatures checks whether a prescribed set $B$ of bugs, located in the intervals of $ℐ$, yields a Partial Surveillance System (PSS) for ${ℐ}_i=\{I_1,\mathrm{\dots },I_i\}$. If so, the algorithm returns the bug-signature list $ℬ$, which coincides with the signature list $𝒮$ defined in the statement of Lemma 8.

The input to the procedure ComputeSignatures consists of: a set of intervals (safe houses) $ℐ=\{I_1,\mathrm{\dots },I_m\}$; a vector $\text{k}=(k_1,\mathrm{\dots },k_m)$ of integers; and an index $i\in [m]$. The vector k specifies a candidate set of bugs $B$ with the associated locations: specifically, it indicates how many bugs are placed in each safe house.

The algorithm begins by assigning identifiers to the bugs in increasing order (lines 1–4), consistently with the ordering (2). The sets $B_j$ record the bugs located in each interval $I_j$. Next, for each $j\in [m]$, the procedure constructs the set ${\mathrm{\Sigma }}_j$ of all bugs able to listen to $I_j$ (lines 5–7). Finally, the intervals are processed in timeline order. For each $I_j$, the algorithm selects the lexicographically smallest signature (according to Definition 3) on ${\mathrm{\Sigma }}_j$ with $S_j\ne S_1,\mathrm{\dots },S_j\ne S_{j-1}$, provided such a signature exists (line 9). If no admissible signature remains ($S_j=null$), then no Surveillance System on $ℐ$ can be obtained using the multiplicities prescribed by k, and the algorithm returns false. Otherwise, it returns true together with the list $ℬ$ of the distinct nonempty bug signatures assigned to the intervals $I_1,\mathrm{\dots },I_i$.

It is important to note that the algorithm only needs to look for the first signature in lexicographic order that does not belong to $\{S_1,\mathrm{\dots },S_{j-1}\}$. Since at most $j-1$ signatures are excluded, it suffices to generate up to the first $j$ signatures on ${\mathrm{\Sigma }}_j$ in lexicographic order.

The signatures constructed by the algorithm exactly match the choice described in Lemma 8, namely, each signature $S_j$ is the lexicographically smallest one (according to Definition 3) on ${\mathrm{\Sigma }}_j$ avoiding the previously assigned signatures $\{S_1,\mathrm{\dots },S_{j-1}\}$. As a consequence, Lemma 8 immediately implies the correctness of ComputeSignatures, formally stated in Lemma 9.

We assume that k yields a PSS for ${ℐ}_{i-1}$. Let $𝒮=(S_1,\mathrm{\dots },S_{i-1})$ be a list of nonempty, pairwise distinct signatures assigned to the intervals of ${ℐ}_{i-1}$ and associated with k. By adding one additional bug $b$ to $I_{q(i)}$, we obtain the new signature $\{b\}$, which is available for $I_i$ and distinct from $S_j$ for every $j\in [i-1]$. Therefore, the updated vector ${\text{k}}^{\prime }$ yields a PSS for ${ℐ}_i$. $◀$

Hence, at the end of the for-loop (lines 2–6), we have that the vector k yields a SS for $ℐ$. The procedure ComputeSignatures is then invoked once more (line 7) to compute the signature $ℬ$ associated with each interval in $ℐ$.

The following theorem establishes that the Surveillance algorithm is a 2-approximate algorithm.

Let $\text{k}=(k_1,k_2,\mathrm{\dots },k_m)$ be the vector returned by the algorithm, and let $ℬ=(S_1,\mathrm{\dots },S_m)$ denote the corresponding list of signatures (chosen according to lexicographic order). Let $\text{o}=(o_1,o_2,\mathrm{\dots },o_m)$ be an optimal solution, and let $𝒞=(C_1,C_2,\mathrm{\dots },C_m)$ be the list of associated signatures (chosen according to lexicographic order).

We show that o and $𝒞$ can be transformed into k and $ℬ$, respectively, by adding some bugs in o. We refer to the bugs present in the optimal solution o as original bugs and to the additional ones as cloned bugs. We show that at the end of the process, there is at most one cloned bug for each original one. This implies that k yields a 2-approximate solution.

We transform o and $𝒞$ step by step, starting from ${\text{o}}^{(0)}=\text{o}$, to ${\text{o}}^{(1)},{\text{o}}^{(2)},\mathrm{\dots }$, ${\text{o}}^{(m)}=\text{k}$. Similarly, we will have ${𝒞}^{(0)}=𝒞$, to ${𝒞}^{(1)},{𝒞}^{(2)},\mathrm{\dots }$, ${𝒞}^{(m)}=ℬ$. We denote by ${\mathrm{\Omega }}_j$ the set of bugs that can listen to $I_j$ at the current iteration, according to ${\text{o}}^{(i)}$; we stress that the bugs are identified with integers from $1$ to ${\sum }_{\mathrm{\ell }=1}^m{o}_{\mathrm{\ell }}^{(i)}$ and are ordered according to (2). The following invariants are maintained by each ${\text{o}}^{(i)}$ and the list of associated signatures ${𝒞}^{(i)}$.

We recall that by construction, Algorithm Surveillance places bugs only in safe houses indexed by elements of $Q$. Moreover, for each we have $q(j)\ge q(1)$, and thus $k_j=0$, while $k_{q(1)}>0$ (because the first bug is placed in $q(1)$).

Starting from ${\text{o}}^{(0)}=\text{o}$, we shift all bugs located in $I_1,I_2,\mathrm{\dots },I_{q(1)-1}$ to $I_{q(1)}$. Formally, we define ${\text{o}}^{(1)}=(o_1^{(1)},\mathrm{\dots },o_m^{(1)})$ by

The total number of bugs is unchanged.

We show that ${\text{o}}^{(1)}$ still yields a Surveillance System for $ℐ$. Let $a$ be bug located in $I_p$ with . For any index $j$ such that $a\in {\mathrm{\Omega }}_j$ (i.e., $I_p\cap I_j\ne \mathrm{\varnothing }$), we show that $I_{q(1)}\cap I_j\ne \mathrm{\varnothing }$, which implies that $a$ can be shifted to $I_{q(1)}$.

Since $I_1\cap I_{q(1)}\ne \mathrm{\varnothing }$, by Fact 7, we obtain $I_{q(1)}\cap I_j\ne \mathrm{\varnothing }$.

Since and $I_p\cap I_j\ne \mathrm{\varnothing }$, Fact 7, we obtain $I_{q(1)}\cap I_j\ne \mathrm{\varnothing }$.

Thus, $a$ belongs to ${\mathrm{\Omega }}_j$ also after being shifted to $I_{q(1)}$. Repeating this argument for all such bugs yields the solution ${\text{o}}^{(1)}$.

Since $k_j=o_j^{(1)}=0$ for all , Claim 14-(a) holds.

If $S_1=C_1^{(0)}$, there is nothing to prove and ${𝒞}^{(1)}={𝒞}^{(0)}=𝒞$.
If $S_1$ does not appear in ${𝒞}^{(0)}$, we simply set $C_1^{(1)}=S_1$ and $C_j^{(1)}=C_j^{(0)}$ for each $j>1$.
Otherwise, $S_1$ appears in ${𝒞}^{(0)}$ as $C_t^{(0)}$ for some $t>1$. We show that the signatures assigned to $I_1$ and $I_t$ can be swapped in ${𝒞}^{(0)}$.

By signatures construction and (5), $C_t^{(0)}=S_1\subseteq {\mathrm{\Omega }}_1$; it then suffices to show that $C_1^{(0)}\subseteq {\mathrm{\Omega }}_t$.

We first show that $I_{q(1)}\cap I_t\ne \mathrm{\varnothing }$. Since $C_t^{(0)}=S_1$, each bug $b\in C_t^{(0)}$ can listen to both $I_1$ and $I_t$, and therefore is located in some interval $I_p$ with $p\le q(1)$ such that $I_p\cap I_t\ne \mathrm{\varnothing }$.

If $t\le q(1)$, then $1\le t\le q(1)$ and, since $I_1\cap I_{q(1)}\ne \mathrm{\varnothing }$, Fact 7, we obtain $I_{q(1)}\cap I_t\ne \mathrm{\varnothing }$. Otherwise, if $t>q(1)$, then using and $I_p\cap I_t\ne \mathrm{\varnothing }$, by Fact 7, we obtain $I_{q(1)}\cap I_t\ne \mathrm{\varnothing }$.

Since $C_1^{(0)}\subseteq {\mathrm{\Omega }}_1$, all bugs in $C_1^{(0)}$ are now located in $I_{q(1)}$. Because $I_{q(1)}\cap I_t\ne \mathrm{\varnothing }$, we conclude that $C_1^{(0)}\subseteq {\mathrm{\Omega }}_t$. Therefore, the swap is feasible, we set $C_1^{(1)}=C_t^{(0)}=S_1$, $C_t^{(1)}=C_1^{(0)}$ and $C_j^{(1)}=C_j^{(0)}$ for each $j\notin \{1,t\}$ and Claim 14-(b) holds.

Consider a Surveillance System satisfying Claim 14 for $i-1$; let it be identified by the vector ${\text{o}}^{(i-1)}=(o_1^{(i-1)},\mathrm{\dots },o_m^{(i-1)})$ with associated list of signatures ${𝒞}^{(i-1)}$.

If $q(i)=q(i-1)$, we simply set ${\text{o}}^{(i)}={\text{o}}^{(i-1)}$, moving no bug.

Otherwise, $q(i)>q(i-1)$. We first establish that

To see why, note that Algorithm Surveillance introduces a bug only when necessary: specifically, a bug placed at interval $I_{q(i-1)}$ must appear in one of the signatures $S_1,\mathrm{\dots },S_{i-1}$. By the inductive hypothesis, $ℬ$ and ${𝒞}^{(i-1)}$ share the first $i-1$ signatures; consequently, every bug counted in $k_1+\mathrm{\cdots }+k_{q(i-1)}$ must also be counted in $o_1^{(i-1)}+\mathrm{\cdots }+o_{q(i-1)}^{(i-1)}$. Moreover, by Claim 14-(a), $k_j=o_j^{(i-1)}$ for all . Inequality (6) follows directly.

We now shift all the bugs located in intervals $I_{q(i-1)+1},\mathrm{\dots },I_{q(i)-1}$, together with $o_{q(i-1)}^{(i-1)}-k_{q(i-1)}$ bugs at $I_{q(i-1)}$, to $I_{q(i)}$. Formally, we define ${\text{o}}^{(i)}=(o_1^{(i)},\mathrm{\dots },o_m^{(i)})$ as follows:

Clearly, the total number of bugs is preserved. We stress that after the shifts in (7), any bug located in an interval $I_j\prec I_{q(i)}$ will not be shifted anymore. Recalling that the bugs are numbered from 1 to ${\sum }_{\mathrm{\ell }=1}^m{o}_{\mathrm{\ell }}^{(i)}$ and ordered according to (2), this also implies that from now

We show now that Claim 14 holds for ${\text{o}}^{(i)}$.

Let $a$ be any bug originally located in an interval $I_p$, with according to ${\text{o}}^{(i-1)}$. Suppose $a$ is one of the bugs that are shifted to $I_{q(i)}$. We show that shifting $a$ preserves the feasibility of the Surveillance System.

To this aim, consider any index $j$ such that $a\in {\mathrm{\Omega }}_j$ (i.e., $I_p\cap I_j\ne \mathrm{\varnothing }$).

By construction, the signatures $S_1,\mathrm{\dots },S_{i-1}$:

• $\mathrm{■}$

  do not contain any bug located in intervals $I_h$ with $h>q(i-1)$. Indeed, any interval in $\{I_1,\mathrm{\dots },I_{i-1}\}$ is disjoint from every interval in $\{I_{q(i-1)+1},\mathrm{\dots },I_m\}$; therefore, bugs located in $I_{q(i-1)+1},\mathrm{\dots },I_m$ cannot listen to any interval among $I_1,\mathrm{\dots },I_{i-1}$;

• $\mathrm{■}$

  use at most $k_{q(i-1)}$ bugs located in $I_{q(i-1)}$.

Since $ℬ$ and ${𝒞}^{(i-1)}$ coincide on the first $i-1$ signatures, we retain exactly $k_{q(i-1)}$ bugs in $I_{q(i-1)}$ and shift all the bugs that are not contained in $S_1,\mathrm{\dots },S_{i-1}$. Summarizing, any shifted bug does not appear in any signature $C_j^{(i-1)}$ with .

Since $I_i\cap I_{q(i)}\ne \mathrm{\varnothing }$ and $i\le j\le q(i)$, by Fact 7, we obtain $I_{q(i)}\cap I_j\ne \mathrm{\varnothing }$. Hence, $a$ remains in ${\mathrm{\Omega }}_j$ after the shift.

Since and $I_p\cap I_j\ne \mathrm{\varnothing }$, by Fact 7, we obtain $I_{q(i)}\cap I_j\ne \mathrm{\varnothing }$. Again, $a$ remains in ${\mathrm{\Omega }}_j$ after the shift.

Repeating this argument for all shifted bugs yields ${\text{o}}^{(i)}$.

If $q(i)=q(i-1)$, the claim follows immediately from the inductive hypothesis. Otherwise, Claim 14-(a) holds for all by induction. Moreover, by (7) we have $o_{q(i-1)}^{(i)}=k_{q(i-1)}$ and $o_j^{(i)}=k_j=0$ for . Hence, Claim 14-(a) holds for $i$.

By the inductive hypothesis, $S_1=C_1^{(i-1)},\mathrm{\dots },S_{i-1}=C_{i-1}^{(i-1)}$.

1. 1)

   If $S_i=C_i^{(i-1)}$, there is nothing to prove and ${𝒞}^{(i)}={𝒞}^{(i-1)}.$

2. 2)

   If $S_i$ does not appear in ${𝒞}^{(i-1)}$, we simply set $C_i^{(i)}=S_i$ and $C_j^{(i)}=C_j^{(i-1)}$ for all $j\ne i$.

3. 3)

   Otherwise, $S_i=C_t^{(i-1)}$ for some $t>i$. by (8), we know that $C_t^{(i-1)}=S_i\subseteq {\mathrm{\Sigma }}_i\subseteq {\mathrm{\Omega }}_i$. Hence, we can again set $C_i^{(i)}=C_t^{(i-1)}=S_i$ and $C_j^{(i)}=C_j^{(i-1)}$ for all $j\notin \{i,t\}$. However, we need $C_t^{(i)}$.
   To this aim, denote by $b$ the smallest bug in $C_t^{(i-1)}$.

   1. 3.1)

      If there exists a signature $S$ in which the smallest bug is $b$ such that $S\subseteq {\mathrm{\Omega }}_t$ and $S\notin {𝒞}^{(i-1)}$, we assign $C_t^{(i)}=S$.

   2. 3.2)

      Otherwise, a new bug $\tilde{b}$ (hereafter, the clone of $b$) is located in the interval $I_{q(i)}$. Let $b$ be located in the interval $I_{\mathrm{\ell }}$, since $b\in C_t^{(i-1)}=S_i$ we know that $I_i\cap I_{\mathrm{\ell }}\ne \mathrm{\varnothing }.$ Recalling that $I_{q(i)}$ is rightmost interval intersecting $I_i$, we know that $\mathrm{\ell }\le q(i)$. Moreover, since $C_t^{(i-1)}=S_i$ we have $I_t\cap I_{\mathrm{\ell }}\ne \mathrm{\varnothing }$. Hence we have $I_t\cap I_{q(i)}\ne \mathrm{\varnothing }$ and we set $C_t^{(i)}=C_t^{(i-1)}\cup \{\tilde{b}\}$.
      We observe that $\tilde{b}$ is located in $I_{q(i)}$ and $b$ is located in $I_{\mathrm{\ell }}$ with $\mathrm{\ell }\le q(i)$. Hence, we may assume that $b\prec \tilde{b}$ and $b$ is still the smallest bug in $C_t^{(i)}$.
      We also notice that for any $t^{\prime }>i$ such that $b\in C_{t^{\prime }}$, the interval $I_{t^{\prime }}$ intersects the interval $I_{\mathrm{\ell }}$ containing $b$. Because $q(i)\ge \mathrm{\ell }$, the interval $I_{q(i)}$ also intersects $I_{t^{\prime }}$. This implies that at any subsequent step $i^{\prime }$, we can still use the clone $\tilde{b}$ located in $I_{q(i)}$ to eventually construct a signature $C_{t^{\prime }}^{(i^{\prime })}$; that is, Case 3.2) cannot occur again, and no bug cloning is required.

   If case 3.2) applied, we added a new bug $\tilde{b}$ located in $q(i)$, we have $o_{q(i)}^{(i)}=o_{q(i)}^{(i)}+1$. To maintain the identifiers of the bugs in increasing order according to the ordering (2), we update the bugs identifier and the signatures in ${𝒞}^{(i)}$ consistently. We notice that since $\tilde{b}$ is located in $q(i),$ this update affects only the identifiers of the bugs located in intervals after $q(i)$ and consequently does not affect any signature before $C_j^{(i)}$ with .

Let $k^{\ast }$ be the size of the optimal solution. Initially, all signatures contain only the $k^{\ast }$ original bugs of the optimal solution. Moreover, we have already observed that, after cloning a bug $b$, any interval containing $b$ will not require a new cloned bug, e.g., Case 3.2) occurs at most once for each original bug and consequently, the total number of clones is at most $k^{\ast }$.
In conclusion, when reaching ${\text{o}}^{(m)}$, we have $k_j=o_j^{(m)}$ for all , and ${𝒞}^{(m)}$ coincide with $ℬ$. Since $ℬ$ uses all and only the bugs described by k and ${\text{o}}^{(m)}$ contains at most $k^{\mathbf{\ast }}$ clones, we conclude that k yields a 2-approximate solution.

The algorithm ComputeSignatures needs $O(m^3)$ time. The initialization of the variables (lines 1–4) takes $O(m)$ time. Computing the neighborhoods requires $O(m^2)$ time. The computation of all sets ${\mathrm{\Omega }}_j$, for $j\in [m]$, also takes $O(m^2)$ time in total.
As observed above, to compute a signature $S_j$, since at most $j-1$ signatures are excluded, it suffices to generate the first $j$ signatures over ${\mathrm{\Sigma }}_j$ in lexicographic order and return the first one that is not excluded. The signatures over ${\mathrm{\Sigma }}_j$ can be generated by a straightforward algorithm that performs an iterative depth-first traversal with a preorder visit of the implicit lexicographic tree of subsets of ${\mathrm{\Sigma }}_j$. Since the size of any signature is at most (a trivial solution, placing one bug in each safe house, each tuned only to its own house, is always feasible), generating and checking a single signature requires $O(m)$ time. Therefore, generating the first $j$ signatures over ${\mathrm{\Sigma }}_j$ takes $O(jm)$ time. Summing over all $j\in [m]$, the total time spent generating signatures is $O(m^3)$. Hence, the total running time of ComputeSignatures is $O(m^3)$.

The time complexity of Algorithm Surveillance is $O(m^4)$. Indeed, the algorithm invokes ComputeSignatures a total of $m+1$ times, and the computation of $h$, performed at most $m$ times, requires $O(m^2)$ time.

By using appropriate data structures for the generation and checking of signatures or by means of an amortized analysis, this time complexity can be reduced to $O(m^3)$. $◀$ Moral of the story: in Cold War Berlin, as in algorithms, a small amount of redundancy along the timeline buys you certainty at only twice the cost.