Randomized Binary and Tree Search Under Pressure

Our paper studies a models where the seeker must certify exactly the position of the target at the end of the procedure. Guessing the target at the end – without spending queries to certify it – yields zero profit. This feature is motivated by cases where the seeker is accountable for actions taken after the target is found, which include, e.g., forcing quarantines or other extreme measures. It is interesting to consider extensions, where some profit might be gained depending on the size of the target’s range after the $k$ queries. We leave such models for future work.

Previous literature mostly focuses on minimizing the worst-case number of queries needed to find the target. When the target is hidden in a tree, Lam and Yue [22] (see also [15]) provide a linear time algorithm which generates an optimal search tree for the edge query model, a result that was later rediscovered in a sequence of papers, including the works by Ben-Asher et al. [3], Onak and Parys [27], and Mozes et al. [25]. A more general setting was later considered by Cicalese et al. [12] where each edge has a different cost. The objective is to find the target with the worst-case minimum total cost. This version turns out to be strongly NP-hard and admits an approximation algorithm with a slightly sublogarithmic approximation factor.

An alternative model considers queries on the vertex of the tree. If the target is not in the queried vertex, one learns which of the neighbors is closest to the target. For this model, Schäffer [29] provides a linear-time algorithm generating an optimal search tree. Minimizing the number of vertex queries on an arbitrary undirected graph becomes quite intriguing. There is an $O(m^{\log n}\cdot n^2\log n)$-time algorithm, where $m$ is the number of edges and $n$ the number of vertices. The quasi-polynomial dependency is necessary, as there is no $O(m^{(1-ϵ)\log n})$-time algorithm under the Strong Exponential-Time Hypothesis (SETH) [18]. For directed acyclic graphs, a vertex query returns 3 types of answers: the target is on the queried vertex, the target is reachable from the queried vertex, or it is not. In this model, minimizing the number of queries is NP-complete [9].

A different line of research considers a known probability distribution of the position of the target, and aims to find a search strategy (either for node or edge queries) that minimizes the expected number of queries until the target is found. Knuth [21] shows that dynamic programming can solve this problem on the line with running time $O(n^2)$, while Mehlhorn [24] shows that bisecting the probability mass in each iteration yields a constant-factor approximation algorithm. For the more complicated problem on trees in the edge query model, Cicalese et al. [10, 11] shows that finding an optimal search strategy is NP-hard. Moreover, it admits a 1.62-approximation algorithm and even an FPTAS on trees of bounded degree. On the other hand, for node queries, the complexity of the problem is still open. Recently, Berendsohn and Kozma [5] show that the problem admits a PTAS, and Berendsohn et al. [4] analyze the algorithm that iteratively select the centroid of the tree. Besides given a fast output-sensitive algorithm for finding the centroid, they show that the obtained strategy is a 2-approximation, and that the analysis is tight even when the target distribution is uniform.

We study two scenarios: (i) For the unit profit case on a line, we provide an algorithm that computes the optimal strategy for the seeker in $O(\log n)$ time; (ii) if $G$ is a general tree and the profit $p$ is arbitrary, we show that we can find a Nash equilibrium in time $2^k\text{poly(n)}$ while computing the best response for the seeker is NP-hard.

Our main result is (i). Our algorithm samples a search strategy in time $O(\log n)$ (using $O(\log n)$ random bits). Afterwards, choosing the next edge to query takes constant time. The solution picks a random interval to perform binary search on it. The interval is chosen uniformly at random from a set constructed with a greedy algorithm based on modular arithmetics (see Figure 4). This construction naturally connects to Bezout’s identity and the Extended Euclidean algorithm, which we exploit to obtain the claimed running times. On the other hand, we provide a construction that yields an optimal strategy for the hider, which we then use to show that both strategies (hider and seeker) are optimal by linear programming duality. For some regimes of values of $n$ and $k$, the optimal hider’s solution requires an intricate construction as she needs to unevenly distribute probability mass to avoid giving the seeker an advantage (see Figure 5).

For (ii), where $G=(V,E)$ is an arbitrary tree and $p$ is any non-increasing profit function, we again consider the corresponding zero-sum game as a linear program (LP), which has an exponential number of variables. We show that the separation of the dual problem – the problem of computing the best-response of the hider – can be solved in time $O(n^2{2}^{2k})$. In contrast, when $k$ is part of the input, the separation problem is NP-hard, which justifies the exponential dependency on $k$¹¹1Observe, however, that this does not imply that computing a Nash equilibrium is NP-hard.. The separation problem of the dual takes as input a distribution of the target node over $V$. It consists of finding a search strategy with at most $k$ queries that maximizes the expected profit of the seeker. We devise a dynamic program that solves this problem. It is based on the concept of visibility vectors [22, 27, 15], introduced for the problem of minimizing the time to find the target in the worst-case. By rooting the tree, we can apply a bottom-up approach to extend a solution for each possible visibility vector. The exponential dependency on $k$ comes from the fact that the number of different visibility vectors is exponential in $k$. Together with the Ellipsoid method, we obtain an algorithm to compute a Nash equilibrium in time $2^k\text{poly}(n)$.

Observe that in regimes where the budget is logarithmic, $k\le C\cdot {\log }_2(n)$, then our algorithm for the separation problem runs in polynomial time $O(n^{2+2C})$. Moreover, $k$ is logarithmic in many natural cases. For example, if $G$ has maximum degree $d$ and we are in the unit profit case, then there are search strategies that can unequivocally find the target within $O(d\log n)$ queries [3, 18]. Therefore, if $d$ is a constant, our model only makes sense when $k$ is at most logarithmic, as otherwise we have a strategy that finds the hider with probability 1. Hence, for these cases we can assume that $k\le C\cdot {\log }_2(n)$ and hence our algorithm takes polynomial time $O(n^{2+2C})$. In particular, this yields a running time of $O(n^4)$ for the separation problem when $G$ is a line; which is significantly worse than our dedicated solution.

In Section 2 we introduce the problem formally and discuss the connection with zero-sum games. Our main result is given in Section 3, where we show our solution for the case that $G$ is a path. Finally, Section 4 shows the dynamic program for the general case. Some of the technical details are deferred to the appendix.

For a given search strategy $T$, recall that $C(T)$ represents the set of covered nodes. Much of our technical work is dedicated to show that an optimal randomized solution selects only search strategies where $C(T)$ forms a set of consecutive nodes modulo $n$. For $u,v\in \mathbb{N}$, we define ${[u,v]}_r$ as $\{wmodr:u\le w\le v\}$ if $u\le v$, and ${[u,v]}_r=\mathrm{\varnothing }$ otherwise. For example, ${[3,7]}_5$ is $\{3,4,0,1,2\}$. We refer to ${[u,v]}_r$ as an interval modulo $r$, or simply an interval. To simplify notation, we omit the subscript $r$ when $r=n$, writing $[u,v]$ instead of ${[u,v]}_n$. Additionally, for an integer $\mathrm{\ell }\le r$, we define ${[v\oplus \mathrm{\ell }]}_r={[v,v+\mathrm{\ell }-1]}_r$, which we refer to as the interval that starts at $v$ of length $\mathrm{\ell }$ or simply an interval of length $\mathrm{\ell }$ starting at $v$²²2The length of an interval is not to be confused with the length of a path. The former is given by the number of vertices and the latter by the number of edges in the path.. Observe that this notation describes intervals that “wrap around” the path in a concise manner.

It will be particularly useful to understand the sets that appear as a cover set of a search strategy $T\in {𝒯}_k$. For a fixed value of $k$, for the rest of this section we define $c:=2^k-2$. Observe that a search strategy that aims to cover a single interval in $[1,n-2]$ (i.e., an interval that does not wrap around) is able to cover $c$ nodes: just apply binary search restricted to a given interval of length $c$. On the other hand, if the strategy covers a single (wrap-around) interval that contains either $0$ or $n-1$ (or both), it will cover $c+1$ nodes. Notice also that there cannot be a strategy that covers exactly $[1,c]$, as this immediately implies that $0$ is covered, similarly with $[n-c-1,n-2]$ and node $n-1$. Strategies that cover more than one interval cover a smaller number of nodes. For example, if it covers two disjoint intervals (that do not contain $0$ or $n-1$), the number of covered nodes will be $c-1$; see Figure 3(b). The next proposition formalizes this intuition by giving a characterization of maximal cover sets $C(T)$ (that is, the ones such that there is no $T^{\prime }\in {𝒯}_k$ with $C(T)\subset C(T^{\prime })$) for search strategies $T\in {𝒯}_k$.

The first two conditions in the proposition encompass the fact that the vertices not covered by a search strategy always have at least one neighbor that is also not covered. The third condition states a trade-off between $s$, the number of intervals in $C$, and the cardinality of $C$. Finally, it also says that if $C$ contains $0$ or $n-1$ (or both), the strategy gains an extra covered node. See Figure 3 for an illustration.

Of particular interest are search strategies that cover a single interval, i.e., with $s=1$, as they maximize the number of covered elements. We call such strategies efficient. The following corollary is a direct consequence of Proposition 1.

Due to the first condition of Proposition 1, no efficient strategy covers an interval starting at $1$. For $v\in V\setminus \{1\}$, let $T_v$ be the efficient search strategy that covers $C(T_v)$, as in the corollary.

We will start by constructing a strategy $x={(x_T)}_{T\in {𝒯}_k}\in {\mathrm{\Delta }}_k$ for the seeker given by a greedy algorithm that defines the support of $x$. Given $𝒳:=\text{supp}(x)$, the support of $x$, we will define the probability vector $x$ uniformly over $𝒳$, i.e., $x_T=\frac{1}{|𝒳|}$ if $T\in 𝒳$ and 0 otherwise.

Intuitively, our aim is to cover all nodes as evenly as possible with efficient strategies, that is, by the same number of strategies in $𝒳$. Consider, for example, the case $n=12$ and $k=3$ (i.e., $c=6$), depicted in Figure 5. Imagine that we choose $T_0$ to be in $𝒳$. This alone yields an objective of 0, and hence a natural choice is to consider $𝒳=\{T_0,T_7\}$. However, this implies that nodes in $\{0,1\}$ are covered twice while the rest are covered only once. This imbalance suggests we should add more strategies, the most natural being $T_2$, which produces an imbalance for nodes in $\{8,9,10,11\}$. By continually adding strategies to $𝒳$ in a greedy manner, we obtain the solution in Figure 5, yielding an objective value of ${\min }_v{\sum }_{T:v\in C(T)}{x}_T=5/9$. This example suggests Algorithm 1, which can be interpreted as a greedy rectangle packing algorithm, see Figure 4 and Figure 5.

Observe that in Line 4 of Algorithm 1 we take $v+c$ modulo $n-1$ instead of modulo $n$, which might be counterintuitive. The reason for this choice is that if we remove node $n-1$, then for every $v\notin \{0,1\}$ the cardinality (length) of each set $C(T_v)\setminus \{n-1\}$ is $c$. This avoids the case distinction of Corollary 2.

Given a set $𝒳$, the objective value of $x$ is ${\min }_v{\sum }_{T:v\in C(T)}{x}_T$. If in the while loop we reach the case $v=0$, then the probability of covering vertex $v^{\ast }$ is $|\{T\in 𝒳:v^{\ast }\in C(T)\}|/|𝒳|$, which is the same for every $v^{\ast }$ as each element is covered by the same number of search strategies in $𝒳$. This is the reason why $v=0$ terminates the while loop. If we reach the situation where $v=1$ in the while loop, then we should also stop since $T_1$ is not well defined. We observe that all nodes, except maybe for node $0$, are covered the same number of times by $𝒳$, i.e., $|\{T\in 𝒳:1\in C(T)\}|=|\{T\in 𝒳:v\in C(T)\}|$ for all $v\in V\setminus \{0\}$. We define this quantity as $h:=|\{T\in 𝒳:1\in C(T)\}|$ and we say that it corresponds to the height of $𝒳$. Similarly, let $w=|𝒳|$ denote the cardinality of $𝒳$. With these parameters, the objective value of solution $x$ is $\frac{h}{w}$. The following lemma yields an explicit relationship between $w$ and $h$, and shows how to compute these values with a faster algorithm. In particular, it relates $w$ and $h$ to $\text{gcd}(c,n-1)$, the greatest common divisor of $c$ and $n-1$, and Bezout’s identity. The proof of the lemma is based on the fact that the algorithm indeed finishes and that the values of $h$ and $w$ satisfies the Bezout’s identity $h(n-1)-wc=\text{gcd}(n-1,c)=1$ if $n-1$ and $c$ are coprime. The running times in the next lemma are considered in the RAM model.

If $n-1$ and $c$ are not coprime, Lemma 3 implies that the objective value of the solution $x$ computed by Algorithm 1 equals $\frac{c}{n-1}$. In what follows we will explicitly define a solution $y$ for the dual [D] with the same objective function, thus implying optimality of $x$ and $y$. The dual solution that we will analyze is defined as

for all $v\in V$, where $w=(n-1)/d$ and $d=\text{gcd}(c,n-1)$. We can interpret this solution by thinking of the vertices $\{1,\mathrm{\dots },n-1\}$ as divided into $w$ segments, each containing vertices $kd+1,\mathrm{\dots },kd+d$ for $k=0,\mathrm{\dots },w-1$. Within each segment, the probability mass of $1/w$ is uniformly distributed among its first $d-1$ vertices (see Figure 4). Although this interpretation may seem somewhat contrived, it serves to highlight the connection to the construction of the coprime case, which relies heavily on the use of segments.

In what follows we show that $y$ is indeed a probability distribution with objective value $\frac{c}{n-1}$.

For a set $S\subseteq V$, let $y(S)={\sum }_{v\in S}{y}_v$. To prove the theorem, observe that by weak duality the objective value of $y$ cannot be smaller than $\frac{c}{n-1}$. Hence, it suffices to show that $y(C(T))\le \frac{c}{n-1}$ for all $T\in {𝒯}_k$. Also, observe that as $d$ is a divisor of $n-1$, it holds that $y_{n-1}=0$. Hence, it suffices to analyze the set $C(T)\setminus \{n-1\}$. Recall that ${[u,v]}_r$ denotes the interval $\{u,\mathrm{\dots },v\}$ modulo $r$. Also, notice that $C(T_v)\setminus \{n-1\}={[v\oplus c]}_{n-1}$, for all $V\setminus \{0,1\}$ and $C(T_0)\setminus \{n-1\}={[0\oplus (c+1)]}_{n-1}$. The next lemma will be useful to compute $y(C(T))$ if $T$ is an efficient strategy.

It remains to show optimality of the solution $x$ in the case gcd$(c,n-1)=1$. We define a solution $y$ which assigns probability $0$ to the border cells $0$ and $n-1$. The remaining cells are partitioned into $w$ segments, and a probability mass $1/w$ is uniformly distributed among the cells of each segment, see Figure 5.

The idea for the definition of the segments is as follows. Ideally, we would like to assign a mass of $\frac{h}{wc}$ to each coordinate $y_v$. In this way, each efficient strategy $T\in {𝒯}_k$ of length $c$ would capture a probability of $\frac{h}{w}$. However, this simple idea must be refined as there are issues with the boundary, where efficient strategies have length $c+1$. To handle this situation we define a function $g:V\to \mathbb{Q}$, the ideal mass function, $g(v):=v\cdot \frac{h}{wc}.$ The general idea is that, for any vertex $v\in [1,n-2]$, the cumulative mass of the solution $y$ up to $v$ remains bounded by To satisfy this property, we partition nodes in $[1,n-2]$ into $w$ segments of two possible lengths: $r:=\lfloor \frac{c}{h}\rfloor$ or $r+1$ (where length refers to the number of nodes in a segment).

To define the segments start at node $v=1$, and choose the largest $r^{\ast }\in \{r,r+1\}$ such that

then, $r^{\ast }$ is the length of the segment starting at $v$. Set $y_i=\frac{1}{r^{\ast }w}$ for $i\in [v\oplus r^{\ast }]$. Update $v=v+r^{\ast }$ and repeat the same selection rule until $v>n-2$. We call Equation (5) the segment rule.

The constructed $y$ can be used to establish the optimality of $x$. To do so, we need to show that the seeker cannot capture more than $h/w$ probability mass from $y$ with any strategy in ${𝒯}_k$. The proof is given in the full version [8]. It follows a similar structure as for the non-coprime case. However, as the segments are not of uniform length, the analysis is significantly more technical. Combining both cases, coprime and non-coprime, allows to conclude our main theorem.