# Searching in trees with monotonic query times111Some results of this work
have been presented at the 47th International Symposium on Mathematical
Foundations of Computer Science (MFCS 2022) [20]. 222Partially supported by
National Science Centre (Poland) grant number 2018/31/B/ST6/00820.

Dariusz Dereniowski Faculty of Electronics, Telecommunications and
Informatics, Gdańsk University of Technology, Poland Izajasz Wrosz Faculty of
Electronics, Telecommunications and Informatics, Gdańsk University of
Technology, Poland Intel, Poland

###### Abstract

We consider the following generalization of binary search in sorted arrays to
tree domains. In each step of the search, an algorithm is querying a vertex
$q$, and as a reply, it receives an answer, which either states that $q$ is
the desired target, or it gives the neighbor of $q$ that is closer to the
target than $q$. A further generalization assumes that a vertex-weight
function $\omega$ gives the query costs, i.e., the cost of querying $q$ is
$\omega(q)$. The goal is to find an adaptive search strategy requiring the
minimum cost in the worst case. This problem is NP-complete for general weight
functions and one of the challenging open questions is whether there exists a
polynomial-time constant factor approximation algorithm for an arbitrary tree?
In this work, we prove that there exist a constant-factor approximation
algorithm for trees with a monotonic cost function, i.e., when the tree has a
vertex $v$ such that the weights of the subsequent vertices on the path from
$v$ to any leaf give a monotonic (non-increasing or non-decreasing) sequence
$S$. This gives a constant factor approximation algorithm for trees with cost
functions such that each such sequence $S$ has a fixed number of monotonic
segments. Finally, we combine several earlier results to show that the problem
is NP-complete when the number of monotonic segments in $S$ is at least $4$.

Keywords: binary search, graph search, approximation algorithm, query
complexity

##  1 Introduction

Searching plays a central role in computer science due to its ubiquitous real-
world applications as well as its inherent relation to other problems. Many
fundamental computational problems, e.g. sorting, can be formulated as
searching for an element in an appropriately defined set or apply searching as
a subroutine. See for example the classic book [29] or a recent work on
relation between sorting and binary search trees [5]. The search problem, both
in the real world as well as in abstract terms, typically consists of a search
space (e.g., a set, a house, a graph), a search target (vertex, or car keys)
and a searcher that follows some search strategy. In the engineering of data
management systems, searching information efficiently is essential for
achieving high performance. Problem-solving by searching is a well established
approach in artificial intelligence [40]. In operations research, algorithmic
techniques applied to searching significantly improved efficiency of searching
for submarines [25], to give one example. On the other hand, the works on the
naval applications contributed to formulation of numerous theoretical models
of search games, e.g., the binary search game.

An important aspect of any search models is the amount of information
available to the search agent about the potential location of the search
target [40]. The _uninformed search_ model is such that no additional
information is available beyond the definition of the search space. The depth-
first- or breadth-first-search and related models are examples of uninformed
search algorithms. On the other hand, the _informed search_ models assume that
some additional information is available to the search agent. The additional
information can be exploited to construct significantly faster search
strategies. In practical setting, the additional information comes from
exploiting the context of the search problem, e.g., an assumption that alike
elements according to some similarity measure are _close_ to each other,
another practical example is an assumption that elements of the search space
are sorted. In a theoretical setting, the additional information can be
modeled as an heuristic function or an oracle.

In the category of the informed search models we can further characterize the
search models in terms of _when_ the additional information is exploited.
I.e., we can first calculate a search strategy, e.g., in a form of a decision
tree, based on the definition of the search space, which later would be used
to locate arbitrary elements of the search space. Using the terms of
supervised machine learning, we first learn the search model, which is then
being inferred when searching for particular search targets. Consequently, the
optimization criteria may be the time to learn the strategy, the accuracy and
the time of locating particular search targets. In a contrary online approach,
the search strategy is being refined at the same time as locating particular
search targets.

###  1.1 Problem statement

We consider the following search problem defined for a node-weighted tree
$T=(V,E,\omega)$, with a query cost function $\omega\colon
V(T)\rightarrow\mathbb{R_{+}}$. The goal is to design an adaptive algorithm
that we call a _search strategy_ or just _strategy_ for short. The strategy is
divided into steps and in each step it performs a _query_ by selecting some
vertex $q$ of $T$. As an _answer_ it receives information that either $q$ is
the _target_ or otherwise it learns which neighbor of $q$ is closer to the
target.333Alternatively, one may think of the latter as learning which
component of $T-q$ contains the target. In the former case, the search is
completed. The _cost_ of the query is $\omega(q)$.

To formally define the search strategy, consider a node weighted tree
$T=(V,E,\omega)$ and a search target $t\in V(T)$. If $|V(T)|=1$, then search
strategy $\mathcal{A}(T,t)$ is the element $t$ itself. Otherwise, let $q\in
V(T)$ be the vertex that the strategy queries first when searching in $T$, let
$C_{i}$ be the $i$-th connected component of $T\setminus\\{q\\}$. Then, for
$|V(T)|>1$, $\mathcal{A}(T,t)$ is a tuple
$(q,\mathcal{A}(C_{1},t),...,\mathcal{A}(C_{k},t))$, where $k=|N(q)|$ is the
number of neighbors of $q$. We note that this kind of search definition can be
understood as a form of a decision tree.

We denote by $COST(\mathcal{A},t)$ the sum of costs of all queries performed
by a strategy $\mathcal{A}$, when finding $t$. The _cost_ of $\mathcal{A}$ is
defined as $COST(\mathcal{A})=\max_{t\in V}COST(\mathcal{A},t)$. The
optimization criterion asks for a strategy of minimum cost.

One might think about this search process that with each query the search is
narrowed to a subtree of $T$ that can still contain the target. The process is
_adaptive_ in the sense that the choice of the subsequent elements to be
queried depends on the locations and answers of the previous queries. Also, we
consider only _deterministic_ algorithms, where given a fixed sequence of
queries performed so far (and the information obtained), the algorithm selects
always the same element as the next query for a given tree. E.g., the optimal
algorithm for the classic binary search problem on paths that always queries
the median element is adaptive and deterministic. It can be equivalently
stated that the algorithm calculates a _strategy_ for the given input tree,
which encodes the queries to be performed for each potential target.

Our problem is a generalization of the classical binary search, where one
considers trees instead of paths. While also the generalized problem can be
found in the literature under the name of binary search, it might be
illustrative to note that answers to queries over a tree domain are not
necessarily binary (left or right), as the set of possible answers depends on
the degree of the queried vertex.

Figure 1: Binary search on weighted trees. The input tree (a) contains a
target vertex (2), whose position is unknown to the algorithm. Three queries
are performed to the vertices 1, 6, and 7, which incurs the costs of 4, 2 and
1, respectively. The subtrees that contain all vertices that are still
candidates for the target after the first two queries are shown in (b) and
(c).

###  1.2 Paper Organization

The remaining parts of the paper are organized as follows. Section 1.3
explains the motivation for our work. We describe practical applications of
the studied search problem and several use cases for the monotonic structure
of the cost function. Section 1.4 provides a summary of the techniques and
approaches used previously to tackle the problem of binary search in trees.
Section 1.5 describes the main results of this work, which is followed by
Section 1.6 that surveys the related work. Subsequently, in Section 2 we
introduce the notation used in the paper as well as several essential concepts
that are commonly used in the related body of research. In Sections 3 \- 5, we
develop several concepts and techniques (i.e., structured decision trees,
aligned strategies and bottom-up processing). These techniques are later used
in Sections 6 \- 8 where we formulate and analyze algorithms for searching in
trees with different types of monotonic cost functions. Section 10 concludes
the paper, where we propose final remarks and suggest potential directions for
future research.

###  1.3 Motivation and applications

We study a generalization of one of the most fundamental and well known
problems in computer science, i.e., binary search. Since graphs form a natural
abstraction for processes in many domains, our generalization into the domain
of graphs allows us to seek for potential applications of our algorithms and
related problems for example in the domain of large networks analysis [41].
Compared to unordered data structures, it is known that maintaining at least a
partial order over the elements improves the performance of fundamental
operations like search, update or insert, in terms of the number of
comparisons needed [29]. In the context of data management systems, it is
known that efficient indexing is crucial to obtain good performance. Some of
the indexing schemes have the form of a tree, for example the GIndex. At the
same time, calculating optimal search strategies for structures with a partial
order is hard in general [18]. Practical approximation algorithms for
searching in large graphs are important for the advancement of systems focused
on large graph analysis.

Binary search on trees seen as a graph ranking problem (cf. [13]) can be used
to model parallel Cholesky factorization of matrices [15], scheduling of
parallel database queries [33], and VLSI layouts [43]. A more general search
model, i.e., binary search on graphs has been used as a framework for
interactive learning of classifiers, clusterings or rankings [21, 22]. More
applications can be found in software testing [3] or mobile agent computing
[6].

There are several practical applications of searching where the cost of a
query is naturally _higher_ in some central vertex and decreases while moving
towards the leaf nodes of the tree. This occurs naturally when considering
data access times in computer systems, e.g., due to memory hierarchies of
modern processors, characteristics of the storage devices, or distributed
nature of data management systems. In the literature on the binary search
problem, a Hierarchical Memory Model of computation has been studied [1], in
which the memory access time is monotonic with respect to the location of a
data element in the array. Another work was devoted to modeling the problem of
text retrieval from magnetic or optical disks, where a cost model was such
that the cost of a query was monotonic from the location of the previous query
performed in the search process [36]. We also mention an application of tree
domains in automated bug search in computer code [3]. In such case naturally
occurs a possibility that the tree to be searched has the monotonicity
property. In particular, each query represents performing an automatic test
that determines whether the part of the code that corresponds to the subtree
under the tested vertex has an error. Thus, the vertices that are closer to
the root represent larger parts of the code and thus may require more or
longer lasting tests. The scale of exa-scale software applications that may
consist of several tens of separate software packages motivates the use of
advanced software validation strategies, in order to quickly identify software
regressions, e.g., when updating versions of several different packages.

An open question has been posed several times about whether a constant-factor
approximation algorithm exists for arbitrary weight functions, see e.g. [2, 8,
9]. The main motivation of this work is to address this question by finding
natural input instances for which a constant-factor approximation is
achievable. In particular, we give an algorithm for down-monotonic cost
functions and motivated by the theory of parameterized complexity, study a
parameter $k$ of the input instance: the maximum number of monotonic segments
on any path from a central node to any leaf. The case of $k$ equal to the tree
height captures the class of general cost functions. We see this as a step
towards solving the general problem. Our techniques lead to a constant
approximation for any fixed $k$. We believe that this method can be improved
to allow combining segments of different monotonicity, while preserving the
constant factor approximation.

###  1.4 Earlier techniques

Historically, the transition from paths to trees had an intermediate step
where one wants to search partial orders instead of linear ones [32, 35].
Performing comparisons in partial orders leads to a similarly defined graph
problem except that one queries edges instead of vertices. However, each tree
instance for querying edges can be solved via finding an optimal search
strategy for a tree instance with querying vertices [14]. For these reasons,
we consider the more general vertex-query version on trees.

It turns out that our problem reappeared several times in theoretical computer
science under different names. It has been called _LIFO-search_ [24] in the
area of graph pursuit-evasion games, _ordered coloring_ [28], minimum height
elimination trees [7] in the context of parallel matrix factorization, then
vertex ranking [26], and more recently as _tree-depth_ [37].

While listing the main approaches to construct search strategies, we do not
differentiate between the edge and vertex versions of the problem as it turns
out that the algorithmic techniques we mention are applicable to both. The
majority of works, especially for the unweighted version of the problem
utilize the bottom-up tree processing. In this approach one usually assigns
greedily the lowest possible interval and argues that this leads to an optimal
solution, see e.g. [3, 27, 32, 35, 38]. We note here that by ‘interval’ we
mean the following interpretation of the cost function: if costs are seen as
query durations, then the query interval is the corresponding time period in
which the query is processed. The particular contributions of these works
mainly lie in various optimizations that bring down the computational
complexity of finding optimal strategies. In case of non-uniform query times
the problem becomes more challenging and keeping in mind that it is NP-
complete [12] a series of works focused on finding approximate solutions. (We
note that the unweighted case has been long known to be linear-time solvable
[42]). A natural approach, for the case of non-uniform costs, is to query a
‘central’ element of the search space and then computing the strategy
recursively for the remaining subtrees [12, 23], which for trees gives
$\mathcal{O}(\log n)$-factor approximations. More involved recursive
approaches allowed to break the barrier of $\mathcal{O}(\log n)$ in [9, 10]
giving a $\mathcal{O}(\log n/\log\log n)$-approximation. A rather involved
bottom-up approach gave the best approximation ratio of
$\mathcal{O}(\sqrt{\log n})$ so far [14]. The main open question in this line
of research is whether either the edge or vertex query model admits a
polynomial-time constant factor approximation for weighted trees. A possible
angle at tackling this question is to consider either special subclasses of
trees [9] or restricted weight functions [20].

###  1.5 Our results

Given a tree $T=(V,E,\omega)$, we say that a cost function $\omega$ is _up-
monotonic_ (respectively _down-monotonic_) if there exists a vertex $r\in V$
such that for any $u,v\in V$, if $v$ lies on the path between $r$ and $u$ in
$T$, then $\omega(u)\leq\omega(v)$ ($\omega(v)\leq\omega(u)$, respectively).
We say that $\omega$ is _monotonic_ if it is either up-monotonic or down-
monotonic. For this kind of $\omega$ we get the following algorithms.

######  Theorem 1.1.

There exists a linear-time 8-approximation adaptive search algorithm for an
arbitrary tree with up-monotonic cost function.

######  Theorem 1.2.

There exists a polynomial-time $2$-approximation adaptive search algorithm for
an arbitrary tree with down-monotonic cost function.

We say that $\omega$ is _$k$ -monotonic_, $k\geq 1$, if $T$ can be partitioned
into vertex disjoint subtrees $T_{1},\ldots,T_{l}$ such that each of them is
either up-monotonic or down-monotonic, and for some $r\in V$, any path from
$r$ to a leaf in $T$ intersects at most $k$ trees $T_{i}$,
$i\in\\{1,\ldots,l\\}$. By combining Theorem 1.1 and Theorem 1.2, we obtain:

######  Theorem 1.3.

There exists a polynomial-time $8k$-approximation adaptive search algorithm
for an arbitrary tree with a $k$-monotonic cost function.

This implies a constant factor approximation algorithm for instances with
fixed $k$ and raises a question whether the problem is FPT with respect to
$k$? We give a negative answer to this question by proving:

######  Theorem 1.4.

The problem of finding a vertex search strategy for bounded diameter spiders
with $k$-monotonic cost functions is strongly NP-complete for any fixed $k\geq
4$.

A _spider_ is a tree with at most one vertex of degree greater than two.

###  1.6 Related work

One can distinguish three different research directions related to our
problem. We list main results separately for each of those as follows.

Vertex search in trees. It is known that an optimal vertex search strategy can
be computed in linear time for an unweighted tree and this result has been
obtained independently in [42] and in [38]. On the other hand, the weighted
version becomes (strongly) NP-complete and FPT with respect to the maximum
cost444With an assumption of integer-valued cost functions. [18]. For weighted
paths there exists a dynamic programming $\mathcal{O}(n^{2})$-time optimal
algorithm [9] (see also [30]), which although covers graphs of special
structure, is interesting as it may be viewed as the classical binary search
with non-uniform comparison costs. For general trees there is a polynomial-
time $\mathcal{O}(\sqrt{\log n})$-approximation algorithm [14]. The latter is
derived from a QPTAS that for any $0<\varepsilon<1$ gives a
$(1+\varepsilon)$-approximation in time $n^{\mathcal{O}(\log
n/\varepsilon^{2})}$ [14]. We also remark on a closely related problem of
finding, for an arbitrary input graph, its spanning tree that has the minimum
search cost [34]. Another generalization that appeared in the context of
parallel scheduling problems, expressed in our terminology, is to find a
search strategy in which one is allowed to perform several queries
simultaneously [45]. This line of research can be placed in a wider context of
analyzing adaptive algorithms versus some coding schemes and we refer
interested reader e.g. to a much broader survey in [39]. Another related model
of searching in trees is where the weight of each vertex indicates the
likelihood of the vertex being a search target. I.e., this search model can be
considered as a generalization of finding a Binary Search Tree for a path to
the domain of trees [4, 31].

Edge search in trees. The edge search problem on unweighted trees is
essentially different than the vertex search. There has been a series of
papers providing polynomial-time algorithms which eventually lead, again
independently under the names of edge ranking and searching in partial orders,
to linear-time optimal algorithms [32, 35]. Moreover, although this gives the
same complexity as for vertex search, the algorithms themselves were much more
involved and thus the edge search version is more challenging to analyze for
unweighted trees. Despite the fact that the complexity is resolved, upper
bounds on the number of queries have been also developed [16, 23, 33]. We
briefly refer to similar generalizations including spanning tree computations
[33] or the ‘batch’ querying [44]. Interestingly, there is a simple edge-
subdividing reduction making the weighted vertex search more general than the
weighted edge search [14]. However, there is no such transition from non-
weighted edge search to non-weighted vertex search or vice versa. The weighted
edge search is NP-complete for several already restricted classes of trees
[10, 12].

Vertex search in general graphs. We note that our vertex search problem has a
natural reformulation for graphs: a query to a vertex $q$, whenever $q$ is not
the target gives _any_ neighbor of $q$ that is closer to the target than $q$.
This version has been introduced in [23]. It turns out that $\log_{2}n$
queries are enough to perform a search in any graph which gives a quasi-
polynomial algorithm [23]. The same work proves that the weighted version is
PSPACE-complete. See also for further references e.g. [11, 17, 19, 21].

##  2 Definitions and Preliminaries

The set of vertices and edges of a tree $T$ is denoted by $V(T)$ and $E(T)$,
respectively. For a connected subset of vertices $V^{\prime}\subseteq V(T)$ of
$T$, we denote by $T[V^{\prime}]$ the induced subtree of $T$ consisting of all
vertices from $V^{\prime}$. For a rooted $T$, we denote its root by $r(T)$,
while for any $v\in V(T)$, $T_{v}$ is the subtree of $T$ rooted at $v$ which
consists of $v$ and all its descendants. $N(v)$ denotes the set of neighbors
of a vertex $v$.

For any two intervals $I=[a,b)$ and $I^{\prime}=[a^{\prime},b^{\prime})$ we
write $I>I^{\prime}$ ($I<I^{\prime}$) when $a\geq b^{\prime}$ ($b\leq
a^{\prime}$). Thus, whenever $I>I^{\prime}$ or $I<I^{\prime}$, we have $I\cap
I^{\prime}=\emptyset$. For an interval $I=[a,b)$ and a number $c$, we write
$I<c$ ($I>c$), when $b\leq c$ ($a\geq c$, respectively). Furthermore, we
define the sum $I+c$ as the interval $[a+c,b+c)$.

We say that an interval $I=[a,b)$ is _minimal_ (_maximal_) in a given set of
intervals, if and only if for any other interval
$I^{\prime}=[a^{\prime},b^{\prime})$ in the set, we have that $a\leq
a^{\prime}$ (respectively $b\geq b^{\prime}$). Note that every finite set of
intervals contains both a minimal and a maximal interval. In this work, all
intervals we use are left-closed, right-opened, and with integer endpoints.

We extend the classic lexicographic order over sequences of integers, denoted
by binary operator $<_{l}$ to sequences of intervals. For two interval
sequences $S$ and $S^{\prime}$ (each with pairwise disjoint intervals), we
write $S<_{l}S^{\prime}$ if and only if there exists an integer $i$ such that
$i+1\notin\bigcup S$, $i+1\in\bigcup S^{\prime}$ and

$[0,i)\cap\bigcup S=[0,i)\cap\bigcup S^{\prime}.$

We then write $S\leq_{l}S^{\prime}$ if and only if $S<_{l}S^{\prime}$ or
$S=S^{\prime}$.

We use the term _sequence of queries_ to refer to the sequence of vertices
queried by a search strategy $\mathcal{A}$ for a target $t$ and we denote it
by $\mathcal{Q}_{\mathcal{A}}(T,t)$. The vertex queried by $\mathcal{A}$ in
the $i$-th step is denoted by $\mathcal{Q}_{\mathcal{A},i}(T,t)$. Given a
search strategy for $T$, one can easily generate a search strategy for any
subtree $T^{\prime}$ by simply discarding the queries to the vertices outside
of $T^{\prime}$. A useful way of encoding search strategies is by using
decision trees.

######  Definition 2.1.

We define a _decision tree_ for $T=(V,E,w)$ generated by a search strategy
$\mathcal{A}$ as a rooted tree $\mathcal{T}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=V(T)$. The root of $\mathcal{T}$ is the first vertex queried by
$\mathcal{A}$. For any $v\in\mathcal{V}$, $v$ has a child $v^{\prime}$ if and
only if $v^{\prime}$ is queried by $\mathcal{A}$ right after $v$ for some
choice of the target. Each $v\in\mathcal{V}$ corresponds to a subset
$\mathcal{T}(v)\subset V(T)$ which contains all vertices that can still
contain the target when $\mathcal{A}$ queries $v$.

It can be seen that the root $r$ of any decision tree corresponds to
$\mathcal{T}(r)=V(T)$ and the leaves correspond to single vertices in $V(T)$.

Lemma 2.2 shows a property of the decision trees with respect to the positions
of vertices that belong to some connected component of the input tree.

######  Lemma 2.2.

Let $\mathcal{T}$ be a decision tree for $T$. If $T^{\prime}$ is a subtree of
$T$, then there exists a vertex $u\in V(T^{\prime})$, such that for every
$v\in V(T^{\prime})$ it holds $v\in V(\mathcal{T}_{u})$.

###### Proof.

We traverse the decision tree $\mathcal{T}$ starting at the root of
$\mathcal{T}$ and following a path to some leaf. If $r(\mathcal{T})\in
V(T^{\prime})$, then the lemma follows. Otherwise, consider children $v_{i}$
of $r(\mathcal{T})$. Because in $T$ there is only one edge incident to
$r(\mathcal{T})$ that lies on a path to all vertices of $T^{\prime}$, all
vertices of $T^{\prime}$ belong to exactly one subtree $\mathcal{T}_{v_{i}}$.
We continue the traversal in $\mathcal{T}_{v_{i}}$ and set $u$ as the first
visited vertex in this process that belongs to $T^{\prime}$. ∎

We now formally define the cost of a search process, which is the parameter of
$T$ the algorithm aims to minimize. In terms of the search strategy
$\mathcal{A}$ for an input tree $T=(V,E,\omega)$, the sum of costs of all
queries performed when finding a target $t\in V(T)$ is denoted by
$COST(\mathcal{A},t)$, while the _cost_ of $\mathcal{A}$ is defined as
$COST(\mathcal{A})=\max_{t\in V}COST(\mathcal{A},t)$.

Sometimes in our analysis, we will take one decision tree and measure its cost
with different query times, i.e., for different weights. This approach will
allow us to artificially increase the cost of some queries in the decision
tree, which we formalize as follows. Let $\mathcal{T}$ be a decision tree for
$T=(V,E,\omega)$ and $\omega^{\prime}$ an arbitrary cost function defined on
$V(T)$, potentially a different one than $\omega$. We denote by
$COST(\mathcal{T},\omega^{\prime})$ the _cost of the decision tree according
to the cost function_ $\omega^{\prime}$:

$COST(\mathcal{T},\omega^{\prime})=\max\big{\\{}\sum_{v\in
V(P)}\omega^{\prime}(v)\;|\;P\textup{ is a path from the root to a leaf in
}\mathcal{T}\big{\\}}.$

The _cost_ of $\mathcal{T}$ is then $COST(\mathcal{T},\omega)$ and we shorten
it to $COST(\mathcal{T})$. (Note that one may equivalently define the cost of
$\mathcal{T}$ by taking $COST(\mathcal{T})=COST(\mathcal{A})$ where
$\mathcal{T}$ is generated by $\mathcal{A}$.) The minimum cost that is
achievable for $T$ is denoted by

$OPT(T)=\min\\{COST(\mathcal{T})\;|\;\mathcal{T}\textup{ is a decision tree
for }T\\}.$

We say that $\mathcal{T}$ _is optimal_ if and only if
$COST(\mathcal{T})=OPT(T)$.

We will use the following simple folklore lemma whose proof is given for
completeness. Lemma 2.3 has been previously formulated in [9] in the context
of a slightly different problem of edge search in weighted trees.

######  Lemma 2.3.

If $\mathcal{T}$ is a decision tree for $T$, then for any subtree $T^{\prime}$
of $T$ there exists a decision tree $\mathcal{T^{\prime}}$, such that
$COST(\mathcal{T^{\prime}})\leq COST(\mathcal{T})$.

###### Proof.

We first apply Lemma 2.2 and reduce $\mathcal{T}$ to its subtree rooted at
$u\in V(T^{\prime})$. Then, we sequentially remove from $\mathcal{T}_{u}$ all
nodes that do not belong to $T^{\prime}$. For every removed node $v$, consider
all subtrees rooted at the children of $v$ in the current decision tree. When
removing $v$ we also remove all subtrees that do not contain any vertex from
$T^{\prime}$ but we connect the roots of all other subtrees (note that there
will be only one such subtree) directly under the parent of $v$. Hence, the
reduced tree is still a decision tree. What is more, all paths from the root
to a leaf in the obtained decision tree result from corresponding paths from
$\mathcal{T}$ by removing zero or more nodes, which upperbounds the cost of
$\mathcal{T^{\prime}}$ by the cost of $\mathcal{T}$. ∎

We say that a cost function $\omega$ is _rounded_ if the values taken by
$\omega$ are powers of two (for any $v\in V(T)$, $\omega(v)=2^{k}$ for some
$k\in\mathbb{N}$). We also say that $T^{\prime}$ is the _rounding_ of $T$ if
it is obtained from $T$ by rounding the cost function to the closest, greater
power of two. We obtain that $OPT(T^{\prime})\leq 2\,OPT(T)$ because
$\omega^{\prime}\leq 2\omega$. On the other hand, Lemma 2.4 shows how large is
the overhead from applying an optimal decision tree for the input with a
rounded cost function to search through the input tree with the original
weights.

######  Lemma 2.4.

Let $T^{\prime}=(V,E,\omega^{\prime})$ be the rounding of $T=(V,E,\omega)$.
Let $\mathcal{T}$ and $\mathcal{T^{\prime}}$ be optimal decision trees
respectively for $T$ and $T^{\prime}$. We have:

$COST(\mathcal{T^{\prime}},\omega)\leq 2\,COST(\mathcal{T})=2OPT(T).$

###### Proof.

We have $COST(\mathcal{T^{\prime}},\omega)\leq
COST(\mathcal{T^{\prime}},\omega^{\prime})\leq
COST(\mathcal{T},\omega^{\prime})\leq 2COST(\mathcal{T},\omega)$. The first
inequality holds because $\omega\leq\omega^{\prime}$. The second inequality
holds because $\mathcal{T^{\prime}}$ is optimal for $T^{\prime}$. The last
inequality holds because $\omega^{\prime}\leq 2\omega$. ∎

###  2.1 Strategy functions

In case of uniform query times, an optimal search strategy can be obtained by
calculating a _strategy function_ $f\colon V(T)\to\mathbb{N}$, where for each
pair of distinct vertices $v_{1},v_{2}\in V(T)$, if $f(v_{1})=f(v_{2})$, then
each path connecting $v_{1}$ and $v_{2}$ has a vertex $v_{3}$ such that
$f(v_{3})>f(v_{1})$. As outlined earlier, methods using functions analogous to
$f$ can be found in the literature on problems such as elimination trees,
vertex ranking [32, 42], tree-depth [37], and others. One property of the
strategy function is that it encodes the (reversed) order of the queries.
E.g., in any sequence of queries, a vertex with a higher value of $f$ is
always queried before those with lower values of the strategy function. Thus,
the maximal value of $f$ over the vertices of a tree is the worst-case number
of queries necessary to search the tree. In order to express the variable
costs of queries we extend the strategy function into an _extended strategy
function_ (see also [12]).

######  Definition 2.5.

A function $f\colon V(T)\to\\{[a,b)\colon 0\leq a<b\\}$, where $\rvert
f(v)\rvert\geq\omega(v)$ for each $v\in V(T)$, is an _extended strategy
function_ if for each pair of distinct vertices $v_{1},v_{2}\in V(T)$, if
$f(v_{1})\cap f(v_{2})\neq\emptyset$, then the path connecting $v_{1}$ and
$v_{2}$ has a $v_{3}$ such that $f(v_{3})>f(v_{1})\cup f(v_{2})$.

We say that an $f$ is _optimal_ for $T=(V,E,\omega)$ if and only if
$\sup\bigcup_{v\in V}f(v)$ is minimal among all extended strategy functions
for $T$.555We note that $\bigcup_{v\in V}f(v)$ is an interval with the left
endpoint equal to $0$ for an optimal $f$. Based on the time interpretation of
strategy functions, optimal functions correspond to optimal strategies.

######  Observation 2.6.

For any $T=(V,E,\omega)$, there exists an optimal extended strategy function
$f$, such that $|f(v)|=\omega(v)$, for every $v\in V(T)$. ∎

###### Proof.

Let $f^{\prime}$ be an optimal extended strategy function for
$T=(V,E,\omega)$, while $v\in V(T)$, an arbitrary vertex such that
$|f^{\prime}(v)|>\omega(v)$. Taking $f^{\prime}(v)=[a_{v},b_{v})$ and
$\delta_{v}=|f^{\prime}(v)|-\omega(v)$, we modify $f^{\prime}$ into $f$ by
setting $f(v)=[a_{v}+\delta_{v},b_{v})$. Because $\sup\bigcup_{v\in
V}f(v)=\sup\bigcup_{v\in V}f^{\prime}(v)$, $f$ is an optimal extended strategy
function for $T$. ∎

Given an extended strategy function $f$ for a node weighted tree
$T=(V,E,\omega)$, one easily obtains a search strategy for the tree by first
locating the vertex $q$ with the maximal interval assigned by $f$. In a
trivial case, where $|V(T)|=1$, this completes the construction of
$\mathcal{A}$. Otherwise, let us first note that there is only one such vertex
$q$ in $V(T)$ with a maximal interval. Assume that there is a $q^{\prime}\in
V(T)$, $q\neq q^{\prime}$, such that $b^{\prime}=b$, where $f(q)=[a,b)$,
$f(q^{\prime})=[a^{\prime},b^{\prime})$. Then, because $f(q)\cap
f(q^{\prime})\neq\emptyset$, by the definition of $f$, on the simple path
between $q$ and $q^{\prime}$, a vertex $p$ would have to exist such that
$f(p)>f(q)\cup f(q^{\prime})$. Consequently, $q$ could not be maximal. By the
same argument, this maximal interval has an empty intersection with intervals
assigned to any other vertex. Let $|N(q)|=k$ and let $T_{i}$ be the $i$-th
component of $T\setminus\\{q\\}$, $i\leq k$. Then, for arbitrary search target
$t$, $\mathcal{A}(T,t)$ is a tuple
$(q,\mathcal{A}(T_{1},t),...,\mathcal{A}(T_{k},t))$. Then, the construction of
$\mathcal{A}$ continues recursively by using $f$ restricted to each component
$T_{i}$.

On the other hand, given a search strategy $\mathcal{A}$, we can obtain an
extended strategy function $f$ that encodes the same sequences of queries as
those made by $\mathcal{A}$. Let $q$ be the vertex queried as first by
$\mathcal{A}$. We set $f(q)=[0,\omega(q))$ in the trivial case, i.e. when
$|V(T)|=1$. If $|V(T)|>1$, let
$\mathcal{A}=(q,\mathcal{A}(T_{1},t),...,\mathcal{A}(T_{k},t))$, $N(q)=k$. We
fix the values of $f$ for all vertices different than $q$ by recursively
repeating the process for the components $T_{i}$. Note that each $v\in V(T)$
is referenced exactly once in $\mathcal{A}$. This is the case, because the
components $T_{i}$ have disjoint vertex sets. After fixing $f$ in the
components, we set $f(q)=[\sup\bigcup_{v\neq q}f(v),\sup\bigcup_{v\neq
q}f(v)+\omega(q))$. We will now show that $f$ is an extended strategy
function. Consider vertices $x\neq y$ in $V(T)$, such that $f(x)\cap
f(y)\neq\emptyset$. Consider the sequences of queries $S_{x}$ and $S_{y}$,
leading respectively to querying $x$ and $y$. Since both $S_{x}$ and $S_{y}$
are generated by the same strategy $\mathcal{A}$, they have a common prefix of
length at least one of identical vertices. Let $v$ be the last vertex in the
prefix. Since $x\neq y$, at least one vertex out of $x$ and $y$ was set after
$v$ by our procedure before both $x$ and $y$. In other words, because $x\neq
y$ only one of them might be $v$. Consequently we have that $f(x)\cup
f(y)<f(v)$.

This also shows that the interval assigned to a vertex $v$ by $f$ might encode
the time interval for querying $v$, where the ‘time’ is understood as dictated
by the precedence relation we use for intervals.

Given an extended strategy function $f$ for $T$, we say that a vertex $u$ is
_visible_ from a vertex $v$ if and only if on the path that connects $u$ and
$v$ there is no vertex $x$ such that $f(u)<f(x)$. The idea of visibility has
been used e.g. in [45] and also earlier under the name of ‘critical lists’ in
[32]. The sequence of values (intervals) visible from $v$ in descending order
is called a _visibility sequence_ (_extended visibility sequence_) for $v$ and
is denoted by $S(v)$. Whenever we need to point out that $S(v)$ is obtained
from a given $f$ in the above way, we say that $S(v)$ is _derived_ from $f$.

The concept of visibility is also used when $f$ is defined only on a subset of
$V(T)$, i.e., on all descendants of some vertex $v$. In this context, which
typically occurs during bottom-up processing of $T$, only those vertices are
considered for which $f$ has been already defined.

We will decide on a strategy function $f(v)$ for each vertex $v$ by assigning
an integer $j_{v}$ to $v$ in a bottom-up processing of the input tree. Each
$j_{v}$ will determine $f(v)$ differently for different vertices. However, the
$j_{v}$ will be computed via an appropriate use of the following operator.

######  Definition 2.7 ([38]).

Let $f$ be a strategy function defined on all descendants of a $v\in V(T)$.
Let $v_{i}$, $1\leq i\leq k$, be the children of $v$. The _vertex extension_
operator attributes $v$ with $f(v)$, based on the visibility sequences
$S(v_{i})$ in the following way. Let $M$ be the set of integers that belong to
at least two distinct visibility sequences $S(v_{i})$, while
$m=\max(M\cup\\{-1\\})$. We set $f(v)$ as the lowest integer greater than $m$
that does not belong to any $S(v_{i})$.

The following lemma characterizes the vertex extension operator.

######  Lemma 2.8 ([38]).

Given the visibility sequences assigned to the children of $v\in V(T)$, the
_vertex extension operator_ assigns to $v$ a visibility sequence that is
lexicographically minimal (the vertex extension operator is minimizing).
Moreover, (lexicographically) increasing the visibility sequence of a child of
$v$ does not decrease the visibility sequence calculated for $v$ (the vertex
extension operator is monotone).

##  3 Structured decision trees

In Sections 3, 4 we consider rooted trees $T=(V,E,\omega)$, in which while
traversing any path from the root to a leaf, the weights of the visited
vertices are non-increasing. In particular, the root of $T$ is selected
properly according to the definition of an up-monotonic cost function. This
section gives a foundation for the algorithm in Section 6.

We define a _layer_ of a tree $T$ as a subgraph $L$ of $T$ such that all
vertices in $V(L)$ have the same cost, $\omega(u)=\omega(v)$ for any $u,v\in
V(L)$. A connected component of $L$ is called a _layer component_. We also
denote by $\omega(L)$ the cost of querying a vertex that belongs to $L$, i.e.,
$\omega(L)=\omega(v)$ for any $v\in V(L)$.

The _upper border_ of a layer $L$ is the set of roots of its layer components.
The subset of $V(L)$ consisting of vertices that have at least one child that
belongs to a different layer is called the _lower border_ of $L$. We will also
say that a layer component $L^{\prime}$ is _directly below_ a layer component
$L$ if and only if $r(L^{\prime})$ has a parent in $L$. The _top_ layer
component is the one that contains the root of $T$ and a _bottom_ layer
component is any $L$ such that there is no component directly below $L$. We
note that we will apply the above terms to a rounded $\omega$.

######  Definition 3.1.

Let $T$ be a tree with a up-monotonic cost function and $\mathcal{T}$ a
decision tree for $T$. Consider a layer component $L$ of $T$. Let $v=r(L)$. We
say that $\mathcal{T}$ is _structured with respect to_ $L$ if for every vertex
$u\in V(T_{v})$, it holds that $u\in V(\mathcal{T}_{v})$. We say that a
decision tree $\mathcal{T}$ for $T$ is _structured_ if and only if
$\mathcal{T}$ is structured with respect to all layer components of $T$.

Informally speaking, in a structured $\mathcal{T}$ we require that each vertex
in the entire subtree $T_{v}$ is below $v$ in $\mathcal{T}$, for each $v$ that
is the root of a layer component. This is one of the central ideas used in the
algorithm for up-monotonic cost functions for the following reason. While
performing bottom-up processing of (an unweighted) $T$ in [38] (and also other
works, e.g. [32]) each vertex $v$ encodes which steps are already used for
queries of the vertices from $T_{v}$. In our case, that is in a weighted $T$,
we need to encode intervals and the technical problem with that is that they
have different durations while moving upwards from one layer component to the
next. Thus, some intervals that are free to perform queries while moving to a
parent of $v$ may be too short due to the weights in the next layer component.
To deal with that, we make $v=r(L)$ also the root of $\mathcal{T}_{v}$. In
this way only one interval, i.e., the one assigned to $v$ needs to be taken
into account while moving upwards.

Our method requires the decision tree to be structured only when processing
the internal components of $T$. By not enforcing structuring with respect to
the top layer component, a potential additive cost of a single query can be
avoided. (This will be reflected in line 2 of Algorithm 2). However, this
optimization does not change the worst-case cost of the strategy. In result,
the decision tree generated by our algorithm is not structured in general.
Although $r(\mathcal{T})$, the first vertex queried by the strategy, always
belongs to the top layer component of $T$, we may have that
$r(\mathcal{T})\neq r(T)$. In contrast, in a structured decision tree we
always have a stronger property, namely $r(\mathcal{T})=r(T)$.

It turns out in our analysis that considering only structured decision trees
introduces an overall multiplicative cost of $2$ to the performance of the
algorithm:

######  Lemma 3.2.

Let $T=(V,E,\omega)$ be a tree with a up-monotonic and rounded cost function.
There exists a structured decision tree $\mathcal{T^{\prime}}$ for $T$, such
that $COST(\mathcal{T^{\prime}})\leq 2\>OPT(T)$.

###### Proof.

Let $\mathcal{T}$ be any decision tree for $T$. Since $\mathcal{T}$ is
selected arbitrarily, it is enough to prove that
$COST(\mathcal{T^{\prime}})\leq 2\>COST(\mathcal{T})$.

In order to construct the structured decision tree, we traverse $\mathcal{T}$
in a breadth-first fashion starting at the root of $\mathcal{T}$. The
$\mathcal{T^{\prime}}$ is constructed in the process.

By Lemma 2.2, for an arbitrary layer component $L$ of $T$, there exists a
vertex $u^{\prime}\in V(L)$ such that all vertices from $L$ belong to
$\mathcal{T}_{u^{\prime}}$. Among all vertices of $L$, $u^{\prime}$ is visited
first during the traversal.

Consider an arbitrary node $u$ being accessed during the traversal. Let $L$ be
the layer component such that $u\in L$. If $\mathcal{T}$ is structured with
respect to $L$ we continue with the next node. Otherwise (which for a specific
$L$ will happen only once, when $u=u^{\prime}$, as argued in the last
paragraph of the proof), we modify $\mathcal{T}$ by performing the following
steps.

Let $v=r(L)$. We want to replace the subtree $\mathcal{T}_{u}$ with a subtree
consisting of the same nodes but rooted at $v$. Consider a subtree
$T^{\prime}$ of the input $T$, which can still contain the target when the
search process is about to query $u$ according to $\mathcal{T}$. E.g.,
$V(T^{\prime})=V(\mathcal{T}_{u})$. Let $v$ has $k$ neighbors in $T^{\prime}$.
We attach under $v$ the decision trees created with Lemma 2.3 for the $k$
components obtained by removing $v$ from $T^{\prime}$. Lemma 2.3 shows that
the cost of any of the $k$ decision trees is not greater than
$COST(\mathcal{T}_{u})$. Accounting for the cost of $v$, structuring $L$
increases $COST(\mathcal{T})$ no more than $\omega(L)$. Consider an arbitrary
path $P$ from root to a leaf in $\mathcal{T}$. For every node $u\in P$ that
triggers structuring (informally, $u$ is $u^{\prime}$ for some $L$) an
additional node from $L$ is inserted in $P$. Thus, in the worst case, the
weighted length of arbitrary $P$ increases 2 times when transforming
$\mathcal{T}$ into structured $\mathcal{T^{\prime}}$.

By starting the breadth-first traversal at the root of $\mathcal{T}$,
structuring with regards to one layer component does not make $\mathcal{T}$
not structured with regards to any of the previously structured layer
components. ∎

By combining Lemmas 2.4 and 3.2 one obtains Corollary 3.3, which relates the
cost of an optimal decision tree for an input $T$ with the cost of a
structured decision tree obtained through the analysis of the rounding of $T$.

######  Corollary 3.3.

For any tree $T$ with a up-monotonic cost function there exists a structured
decision tree with rounded weights, whose cost is at most $4\cdot OPT(T)$.

##  4 Bottom-up tree processing

We extend the state-of-the-art ranking-based method for searching in trees
with uniform costs of queries [38, 42], where the algorithm calculates a
strategy function $f\colon V(T)\to\mathbb{N}$, given the input tree $T=(V,E)$.
In our approach, to express the variable costs of queries we will use an
interval-based extended strategy function.

Keeping in mind that the cost function is the time needed to perform a query,
the values of an extended strategy function indicate the time periods in which
the respective vertices will be queried. Note that, e.g., due to the rounding,
the time periods will be longer than the query durations and this is easily
resolved either by introducing idle times or by following the actual query
durations while performing a search based on a strategy produced by our
algorithm.

In our approach, informally speaking, we will partition the rounding of the
input tree into several subtrees (the layer components) and for each of them,
we will use the algorithm from [38].

A useful class of extended strategy functions is one that generates decision
trees that are structured (see Definition 3.1).

######  Definition 4.1.

We say that an extended strategy function $f$, defined on the vertices of a
tree $T$ with up-monotonic cost function, is _structured_ if for any layer
component $L$, $f(u)>f(v)$ for each $v\in V(T_{u})$, where $u=r(L)$.

It follows that a structured extended strategy function represents a
structured decision tree.

As mentioned earlier, we will process each layer component $L$ with the vertex
extension operator but in order to do it correctly, we need to initialize
appropriately the roots of the layer components below $L$. For that, we define
the following operators. Let $f$ be an extended strategy function defined on
the vertices of $T_{v}$, where $v$ is the root of a layer component
$L^{\prime}$. The _structuring operator_ assigns to $v$ the minimal interval
so that $f$ is a structured extended strategy function on $T_{v}$. (We note
that in our algorithm $v$ will have some interval assigned when the
structuring operator is about to be applied to $v$. Hence, the application of
this operator will assign the new required interval.) The _cost scaling
operator_ aligns the interval attributed to $v$: if $f(v)=[a,b)$ and $L$ is
the layer component directly above $L^{\prime}$, the cost scaling operator
assigns $v$ the interval
$[\omega(L)\lceil\frac{b}{\omega(L)}\rceil-\omega(L),\omega(L)\lceil\frac{b}{\omega(L)}\rceil)$.
We will say that vertex $v$ is _aligned to_ $\omega(L)$ after this
modification (see the beginning of Section 5 for a formal definition).
Informally speaking, this is done so that the children of the leaves in $L$
have intervals whose endpoints are multiples of $\omega(L)$ so that they
become ‘compatible’ with the allowed placements for intervals of the vertices
from $L$. Yet in other words, this allows us to translate the intervals of the
children of the leaves in $L$ into integers that can be treated during bottom-
up processing of $L$ in a uniform way.

######  Observation 4.2.

Let a layer component $L^{\prime}$ be directly below a layer component $L$ in
$T=(V,E,\omega)$. If $r(L^{\prime})$ is assigned an interval $[a,b)$, whose
endpoints are consecutive multiples of $\omega(L^{\prime})$ (i.e.
$a=k\omega(L^{\prime})$ and $b=(k+1)\omega(L^{\prime})$ for some integer $k$),
then the cost scaling operator assigns to $r(L^{\prime})$ an interval
$[a^{\prime},b^{\prime})$ such that $b^{\prime}\leq
b+\omega(L)-\omega(L^{\prime})$.

###### Proof.

Consider a layer component $L$ of $T=(V,E,\omega)$ and a structured extended
strategy function $f$ defined on the vertices below $L$. The cost scaling
operator selects $b^{\prime}$ as the smallest multiple of $\omega(L)$ that is
greater or equal than $b$. Since $a^{\prime}=b^{\prime}-\omega(L)$, we have
that $a^{\prime}<b$. On the other hand, because $b-a=\omega(L^{\prime})$, $a$
is the highest multiple of $\omega(L^{\prime})$ that is less than $b$.
Subsequently, because $w(L)$ is divisible by $w(L^{\prime})$, we obtain that
$a^{\prime}\leq a$. What follows, $a^{\prime}+\omega(L^{\prime})\leq b$, and
finally $b^{\prime}\leq b+\omega(L)-\omega(L^{\prime})$. ∎

##  5 Aligned strategies

In this section we give foundations for analyzing trees with down-monotonic
cost functions, i.e. where the weights of the visited vertices are non-
decreasing while traversing any path from the root to a leaf. In other words,
we consider rooted trees $T=(V,E,\omega)$, where the root of $T$ is selected
properly according to the definition of a down-monotonic cost function.
Concepts provided in this section are used in Section 7, for the analysis of
Algorithm 3.

The first thing the Algorithm 3 does is to switch from the input tree to its
rounding. Although the terms below apply to general weight functions, we
should remember that they will be applied to the rounded ones in our analysis.

Given an extended strategy function $f$, we say that the vertex $v$ is
_aligned_ if the endpoints of the interval $f(v)$ are multiples of
$\omega(v)$. We also say that $f$ is _aligned_ if all vertices are aligned.

For an extended strategy function $f$, a vertex $u$ is _screening_ a vertex
$v$ if and only if, on the path that connects $v$ and $u$, $u$ is the only
vertex such that $f(v)<f(u)$. In other words, for any path $P$ that starts
with $v$, $u\in V(P)$ is screening $v$ if it is the closest vertex to $v$,
such that $f(v)<f(u)$.

######  Observation 5.1.

If $s,s^{\prime}$ are distinct vertices screening some vertex, then $f(s)\cap
f(s^{\prime})=\emptyset$. ∎

Furthermore, for an arbitrary vertex $v$, the _screening neighborhood_ of $v$
is the set $\textup{scr}(v)\subseteq V(T)$ defined as follows. We have that
$u\in\textup{scr}(v)$ if and only if either $u$ is screening $v$ or the path
that connects $u$ and $v$ has no vertex screening $v$. The subtree
$T[\textup{scr}(v)]$ is denoted by $T_{\textup{scr}}(v)$. For an example see
Figure 2. By definition, we include $v$ to be in $\textup{scr}(v)$. Some of
the properties of the screening neighborhood are as follows.

Figure 2: Example of a screening neighborhood. Labels at the vertices show the
corresponding values of some strategy function. The dashed line encloses the
screening neighborhood of the vertex $v$. The (single) vertex screening $v$ is
filled in black. All remaining vertices visible from $v$ are filled with light
gray. Note that the vertex with label $5>f(v)$ is visible from $v$, although
it does not belong to the screening neighborhood of $v$. All vertices that are
not visible from $v$ are white.

######  Observation 5.2.

If $u\in\textup{scr}(v)$ is a leaf of $T_{\textup{scr}}(v)$, then we have that
$u$ is screening $v$ or is a leaf in $T$ (or both). ∎

As stated in Observation 5.3, it may happen that a vertex is visible from $v$,
but does not belong to $\textup{scr}(v)$. Consider a vertex $u$ visible from
$v$ with $f(v)<f(u)$, and a vertex $u^{\prime}$ such that $u$ lies on the path
between $v$ and $u^{\prime}$ and $f(u)<f(u^{\prime})$. Even if $u^{\prime}$
was visible from $v$ (which then implies $f(v)<f(u^{\prime})$), it would not
belong to $\textup{scr}(v)$. In general, not every vertex visible from $v$
belongs to $\textup{scr}(v)$. At the same time not every vertex in
$\textup{scr}(v)$ must be visible from $v$.

######  Observation 5.3.

If a vertex $u$ is visible from $v$ and $f(u)<f(v)$, then
$u\in\textup{scr}(v)$. ∎

We will several times use an important property that for any
$u\in\textup{scr}(v)\setminus\\{v\\}$, either $f(u)<f(v)$ or $f(v)<f(u)$. This
fact basically allows to simplify arguments by reducing the number of possible
subcases in the following lemmas.

######  Observation 5.4.

For each $u\in\textup{scr}(v)$, $u\neq v$, it holds $f(v)\cap f(u)=\emptyset$.

###### Proof.

By contradiction, assume a $u\in\textup{scr}(v)$ exists such that $f(u)\cap
f(v)\neq\emptyset$. Since $f$ is an extended strategy function, there must be
an $x$ on the path between $u$ and $v$, such that $f(x)>f(v)$. Among all such
vertices $x$ consider one with the maximum value of $f(x)$. This choice
implies that $f(x)>f(v)$ and there is no vertex $y$ on the path between $v$
and $x$ such that $f(y)>f(x)\cup f(v)$. This gives that $x$ is screening $v$
contradicting $u\in\textup{scr}(v)$. ∎

######  Lemma 5.5.

Let $f$ be an extended strategy function for $T=(V,E,\omega)$. Consider an
arbitrary $v\in V(T)$. Let $s_{min}\in\textup{scr}(v)$ be the vertex screening
$v$ with the minimal value of $f$, among all vertices screening $v$. Consider
an arbitrary function $f^{\prime}\colon V(T)\to\\{[a,b)\colon 0\leq a<b\\}$,
$\rvert f^{\prime}(v)\rvert\geq\omega(v)$, which satisfies the following
conditions:

  1. 1.

$f^{\prime}(u)=f(u)$, for any $u\not\in\textup{scr}(v)$,

  2. 2.

$f^{\prime}(u)=f(u)$, if $u\in\textup{scr}(v)$ is screening $v$,

  3. 3.

$f^{\prime}(u)<f(s_{min})$, for any $u\in\textup{scr}(v)$ that is not
screening $v$. (This includes $v$.)

We have the following: if $f^{\prime}$ is an extended strategy function for
$T_{\textup{scr}}(v)$, then $f^{\prime}$ is also an extended strategy function
for the entire $T$.

###### Proof.

The proof is by case analysis dictated by the definition of visibility
function. Consider two vertices $x,y\in V(T)$ such that $x\neq y$ and
$f^{\prime}(x)\cap f^{\prime}(y)\neq\emptyset$. For each possible choice of
$x$ and $y$, we show that on the path connecting $x$ and $y$, there is a
vertex $z$ such that $f^{\prime}(x)\cup f^{\prime}(y)<f^{\prime}(z)$. Note
that based on Observation 5.1, $s_{min}$ is unique in $\textup{scr}(v)$.

  * •

Let $x,y\in\textup{scr}(v)$. By assumption, $f^{\prime}$ is an extended
strategy function for $T_{\textup{scr}}(v)$. Thus, on the path between $x$ and
$y$ there exists a required vertex $z$.

  * •

Let $x,y\not\in\textup{scr}(v)$. For all vertices outside of
$T_{\textup{scr}}(v)$, $f^{\prime}$ is identical to $f$. Because $f$ is an
extended strategy function, there exists $z\in V(T)$, such that $f(x)\cup
f(y)<f(z)$.

    1. 1.

If $z$ is outside of $T_{\textup{scr}}(v)$, then $f^{\prime}(z)=f(z)$ and
consequently $f^{\prime}(x)\cup f^{\prime}(y)<f^{\prime}(z)$.

    2. 2.

If $z\in\textup{scr}(v)$ and $z$ is screening $v$, then also in this case
$f^{\prime}(z)=f(z)$ and consequently $f^{\prime}(x)\cup
f^{\prime}(y)<f^{\prime}(z)$.

    3. 3.

If $z\in\textup{scr}(v)$ and $z$ is not screening $v$, let $P$ be the path
connecting $x$ and $y$. (See Figure 3 for an illustration.)

Figure 3: An illustration for the case when $x,y\not\in\textup{scr}(v)$ in
Lemma 5.5.

Because the endpoints $x,y\not\in\textup{scr}(v)$ and $z\in\textup{scr}(v)$ is
not screening $v$, it follows from the definition of $\textup{scr}(v)$ that
$P$ contains vertices $s_{1}$ and $s_{2}$ screening $v$, such that the path
between $s_{1}$ and $s_{2}$ contains $z$. Let
$s=\textup{argmax}_{s\in\\{s_{1},s_{2}\\}}f(s)$. Because $z$ is on a path
either between $v$ and $s_{1}$ or $v$ and $s_{2}$, based on the definition of
a screening vertex, we have that $f(z)<f(s)$. Subsequently, we have that
$f^{\prime}(x)=f(x)<f(z)<f(s)=f^{\prime}(s)$. By similar arguments,
$f^{\prime}(y)<f^{\prime}(s)$. Hence, on the path between $x$ and $y$, $s$ is
the required vertex separating $x$ and $y$.

  * •

Let $x\in\textup{scr}(v)$ and $y\notin\textup{scr}(v)$. Let $P$ be the path
connecting $x$ and $y$. Based on the definition of $\textup{scr}(v)$, $P$
contains at least one vertex screening $v$ (otherwise, for
$x\in\textup{scr}(v)$, $y$ would have to belong to $\textup{scr}(v)$ too). Let
$s\in V(P)$ be the vertex screening $v$ that is closest to $y$. We note that
$P$ contains two vertices screening $v$ only when $x$ is screening $v$.

    1. 1.

Let $x$ be screening $v$. We have $f^{\prime}(x)=f(x)$. Because $f$ is an
extended strategy function for $T$, there is $z\in V(P)$, such that $f(x)\cup
f(y)<f(z)$. We consider two subcases.

Let $x=s$. Recall that $s\in V(P)$ is the vertex screening $v$ that is closest
to $y$. Hence, $x$ is the only vertex in $P$ that belongs to
$\textup{scr}(v)$. Subsequently, $z\notin\textup{scr}(v)$ and we have that
$f^{\prime}(z)=f(z)$. What follows, $f^{\prime}(x)=f(x)<f(z)=f^{\prime}(z)$.

Let $x\neq s$. If $z\notin\textup{scr}(v)$ or $z$ is screening $v$ (i.e.,
$z$=$s$), then $f^{\prime}(z)=f(z)$ and $z$ is the required vertex separating
$x$ and $y$. If $z\in\textup{scr}(v)$ and $z$ is not screening $v$, we have
that $f(z)<f(s)$. What follows, $f^{\prime}(x)=f(x)<f(z)<f(s)=f^{\prime}(s)$.

    2. 2.

If $x$ is not screening $v$, then by definition of $f^{\prime}$ and $s_{min}$,
$f^{\prime}(x)<f^{\prime}(s_{min})\leq f^{\prime}(s)$. What follows, $s$ is
the required vertex separating $x$ and $y$.

∎

The technical Lemma 5.6 shows a property of the screening neighborhood of
specific unaligned vertices. This property is later used in the proof of Lemma
5.7.

######  Lemma 5.6.

Consider an extended strategy function $f$ for $T=(V,E,\omega)$. Let $v\in
V(T)$ be an unaligned vertex, such that $f(v)$ is minimal. Denote
$f(v)=[x_{v},y_{v})$, $|\omega(v)|=2^{k}$. Take $a\in\mathbb{N}$ such that
$a2^{k}<x_{v}<(a+1)2^{k}$. For each $u\in\textup{scr}(v)$ such that
$f(u)\cap[a2^{k},x_{v})\neq\emptyset$, it holds $f(u)\subset[a2^{k},x_{v})$.

###### Proof.

We know that $a$ exists because $v$ is unaligned. By Observation 2.6,
$|f(v)|=2^{k}$. It follows from Observation 5.4 that $f(u)<f(v)$ for any $u$
as in the statement of the lemma, and consequently, that $u$ is aligned.

Let $f(u)=[x_{u},y_{u})$. By assumption and by $f(u)<f(v)$, we know that
$a2^{k}<y_{u}<x_{v}$. Since $u$ is aligned, we have that
$x_{u}=b2^{k^{\prime}}$ and $y_{u}=(b+1)2^{k^{\prime}}$, for some integer
$k^{\prime}$. Note that $a2^{k}<y_{u}<x_{v}<(a+1)2^{k}$ implies
$k^{\prime}<k$. Thus, $y_{u}\geq a2^{k}+2^{k^{\prime}}$, because $u$ is
aligned. This gives $x_{u}=y_{u}-2^{k^{\prime}}\geq a2^{k}$, as required in
the lemma. ∎

We now prove the main result of this section:

######  Lemma 5.7.

For each instance with down-monotonic and rounded cost function, there exists
an optimal extended search strategy function that is aligned.

###### Proof.

In the proof, we consider an optimal extended strategy function $f$, such that
the number of unaligned vertices is minimal. Based on $f$, we construct
another optimal extended strategy function according to which, there are fewer
unaligned vertices. This shows, by contradiction, that there must exist an
optimal extended strategy function such that all vertices are aligned.

Let $v\in V(T)$ be an unaligned vertex, such that the interval $f(v)$ is
minimal. Let $\omega(v)=2^{k}$, $f(v)=[x_{v},y_{v})$. Take $a\in\mathbb{N}$,
such that $a2^{k}<x_{v}<(a+1)2^{k}$ and $(a+1)2^{k}<y_{v}<(a+2)2^{k}$.

Based on the strategy function $f$, we will now construct a $f^{\prime}$ with
fewer unaligned vertices.

  1. 1.

For all $u\notin\textup{scr}(v)$, we set $f^{\prime}(u)=f(u)$.

  2. 2.

If $s\in\textup{scr}(v)$ is screening $v$, we set $f^{\prime}(s)=f(s)$.

  3. 3.

For all other vertices in $\textup{scr}(v)$:

For the $v$ itself, we set $f^{\prime}(v)=[a2^{k},(a+1)2^{k})$.

For any vertex $u\in\textup{scr}(v)$ such that
$f(u)\cap[a2^{k},x_{v})\neq\emptyset$, we set
$f^{\prime}(u)=[x_{u}+2^{k},y_{u}+2^{k})$, where $f(u)=[x_{u},y_{u})$.

For all other vertices $u\in\textup{scr}(v)$ we set $f^{\prime}(u)=f(u)$.

For brevity, we will refer to the vertices $u\in V(T)$ for which
$f^{\prime}(u)\neq f(u)$ as _updated_ vertices. We will refer to all other
vertices as _still_ vertices. A useful fact about the updated vertices is the
following:

  1. (enumi)

We have $f^{\prime}(u)<y_{v}$, for every updated vertex $u\in V(T)$.

By definition of $f^{\prime}$, updated vertices are those whose value of $f$
intersects with $[a2^{k},x_{v})$ or the $v$ itself. The fact (enumi) holds for
$v$. Consider $u\in V(T)$, such that $f(u)\cap[a2^{k},x_{v})\neq\emptyset$.
Denote $f(u)=[x_{u},y_{u})$, $f^{\prime}(u)=[x_{u}^{\prime},y_{u}^{\prime})$.
By Lemma 5.6, we have that $y_{u}\leq x_{v}$. Subsequently,
$y_{u}^{\prime}\leq x_{v}+2^{k}=y_{v}$. This completes the proof of (enumi).

Let us note that $v$ is aligned according to $f^{\prime}$ and all vertices
which were aligned according to $f$ are also aligned according to
$f^{\prime}$. To see the latter, consider an updated vertex $u\neq v$. If $u$
is aligned according to $f$, then by the definition of $f^{\prime}$,
$u\in\textup{scr}(v)$ and $f(u)\cap[a2^{k},x_{v})$. But then, by Lemma 5.6,
$f(u)\subseteq[a2^{k},x_{v})$ which in particular means that $\omega(u)\leq
2^{k}$ and hence $u$ is indeed aligned according to $f^{\prime}$. We also
observe that $\sup{f^{\prime}(v)}<\sup{f(v)}$, and for each $u$, such that
$f(u)\cap[a2^{k},x_{v})\neq\emptyset$, we have
$\sup{f^{\prime}(u)}\leq\sup{f(v)}$. Hence, $f^{\prime}$ is optimal due to the
optimality of $f$. The above in particular implies that it remains to argue
that $f^{\prime}$ is a valid extended strategy function.

We will now show that $f^{\prime}$ is an extended strategy function for $T$.
Based on Lemma 5.5, it suffices to show that $f^{\prime}$ is an extended
strategy function for the subtree $T_{\textup{scr}}(v)$. Consider vertices
$u^{*},v^{*}\in\textup{scr}(v)$, such that $u^{*}\neq v^{*}$ and
$f^{\prime}(u^{*})\cap f^{\prime}(v^{*})\neq\emptyset$. We analyze all
possible choices of the pair $u^{*}$, $v^{*}$. Motivated by Observation 5.4,
we categorize the choices for selecting $u^{*}$ depending on how
$f^{\prime}(u^{*})$ relates to the interval $f(v)=[x_{v},y_{v})$.

Case 1: Let $u^{*}$ be such that $y_{v}<f^{\prime}(u^{*})$. We argue that

$f(v)<f(v^{*})$ (1)

Suppose otherwise, which in view of Observation 5.4 implies $f(v^{*})<f(v)$.
Since $u^{*}$ is still by (enumi), $f(u^{*})=f^{\prime}(u^{*})$. Then,
$y_{v}<f(u^{*})$ can be written as $f(v)<f(u^{*})$. But then $f(v^{*})<f(v)$
gives $f(v^{*})<f(u^{*})$, which contradicts $f(u^{*})\cap
f(v^{*})\neq\emptyset$ and implies (1). The latter and (enumi) prove that
$v^{*}$ is still, thus $y_{v}<f^{\prime}(v^{*})$.

Because $f$ is an extended strategy function, there is a vertex
$z\in\textup{scr}(v)$ on the path between $u^{*}$ and $v^{*}$, such that
$f(z)>f(u^{*})\cup f(v^{*})$. Because $f(z)>f(u^{*})>f(v)$, we have by (enumi)
that $z$ is still. Subsequently,
$f^{\prime}(u^{*})=f(u^{*})<f(z)=f^{\prime}(z)$ and since $v^{*}$ is still
$f^{\prime}(v^{*})=f(v^{*})<f(z)=f^{\prime}(z)$, thus
$f^{\prime}(z)>f^{\prime}(u^{*})\cup f^{\prime}(v^{*})$.

Case 2: Let $u^{*}$ be such that $f^{\prime}(u^{*})<a2^{k}$. By repeating the
steps in Case 1, i.e. when $y_{v}<f^{\prime}(u^{*})$, and using Lemma 5.6, we
obtain that $f^{\prime}(v^{*})<a2^{k}$. Because $f$ is an extended strategy
function, there is a vertex $z\in\textup{scr}(v)$ on the path between $u^{*}$
and $v^{*}$, such that $f(z)>f(u^{*})\cup f(v^{*})$. If $z$ is an updated
vertex, we have that $f^{\prime}(z)>a2^{k}$, hence
$f^{\prime}(u^{*})<f^{\prime}(z)$. Otherwise, we have
$f^{\prime}(u^{*})=f(u^{*})$, and the claim follows from
$f(u^{*})=f^{\prime}(u^{*})$ and $f(v^{*})=f^{\prime}(v^{*})$.

Case 3: Let $u^{*}$ be such that
$f^{\prime}(u^{*})\cap[(a+1)2^{k},y_{v})\neq\emptyset$. Note that $u^{*}\neq
v$ because by definition of $f^{\prime}$, $f^{\prime}(v)=[a2^{k},(a+1)2^{k})$.
Because $f^{\prime}(u^{*})\cap f(v)\neq\emptyset$, it follows from Observation
5.4 that $u^{*}$ is updated. Subsequently, we have that
$f(u^{*})\cap[a2^{k},x_{v})\neq\emptyset$. Based on Lemma 5.6, it holds that
$f(u^{*})\subset[a2^{k},x_{v})$ and subsequently that
$f^{\prime}(u^{*})\subset[(a+1)2^{k},(a+2)2^{k})$. By definition,
$f^{\prime}(v^{*})\cap f^{\prime}(u^{*})\neq\emptyset$. Thus,
$f^{\prime}(v^{*})\cap[(a+1)2^{k},y_{v})\neq\emptyset$. Following the same
steps as for $u^{*}$, we obtain that $v^{*}$ is updated and that
$f^{\prime}(v^{*})\subset[(a+1)2^{k},(a+2)2^{k})$.

Because $f$ is an extended strategy function, there is $z\in\textup{scr}(v)$
on the path between $u^{*}$ and $v^{*}$, such that $f(z)>f(u^{*})\cup
f(v^{*})$. Because both $f(u^{*})$ and $f(v^{*})$ are subsets of
$[a2^{k},x_{v})$, we have that $\omega(u^{*})<\omega(v)$ and
$\omega(v^{*})<\omega(v)$. Because $\omega$ is down-monotonic, we have that
neither $u^{*}$ nor $v^{*}$ belong to $T_{v}$. What follows, $z\neq v$. If $z$
is an updated vertex, then we have $f^{\prime}(z)>f^{\prime}(u^{*})$.
Otherwise, because $z\neq v$, $f^{\prime}(z)=f(z)>y_{v}$, and we have that
$f^{\prime}(u^{*})<y_{v}<f^{\prime}(z)$. Following the same steps for $v^{*}$,
we obtain $f^{\prime}(z)>f^{\prime}(u^{*})\cup f^{\prime}(v^{*})$.

Case 4: Let $u^{*}$ be such that
$f^{\prime}(u^{*})\cap[a2^{k},(a+1)2^{k})\neq\emptyset$. We will start by
showing that this condition holds only when $u^{*}=v$.

Consider the following ways we may choose $u^{*}\in\textup{scr}(v)$, with
respect to the interval $f(u^{*})$:

  1. 1.

$f(u^{*})<a2^{k}$. By definition of $f^{\prime}$, vertex $u^{*}$ is still,
thus $f^{\prime}(u^{*})<a2^{k}$. What follows, such $u$ does not exist.

  2. 2.

$f(u^{*})\cap[a2^{k},x_{v})\neq\emptyset$. By Lemma 5.6, we have that
$f(u^{*})\subset[a2^{k},x_{v})$. By definition of $f^{\prime}$, we have that
$(a+1)2^{k}\leq f^{\prime}(u^{*})$.

  3. 3.

$f(u^{*})\cap[x_{v},y_{v})\neq\emptyset$. Based on Observation 5.4, we have
$u^{*}=v$.

  4. 4.

$y_{v}\leq f(u^{*})$. By definition of $f^{\prime}$, $u^{*}$ is still, thus
$(a+1)2^{k}<y_{v}\leq f(u^{*})=f^{\prime}(u^{*})$.

Subsequently, because $v^{*}\neq u^{*}$, we have that
$f^{\prime}(v^{*})\cap[a2^{k},(a+1)2^{k})=\emptyset$. This shows that it is
not possible to find a $v^{*}\in\textup{scr}(v)$, such that because
$f^{\prime}(u^{*})\cap f^{\prime}(v^{*})\neq\emptyset$. ∎

##  6 The algorithm for up-monotonic cost functions

In this section we propose an algorithm for trees with up-monotonic cost
functions (cf. Algorithm 1). The algorithm starts with a pre-processing pass,
which transforms the input tree to its rounding and selects a root arbitrarily
from the set of vertices with the highest cost o query (cf. definition of an
up-monotonic cost function, Section 1.5). An extended strategy function $f$ is
then calculated during a bottom-up traversal over the layer components of the
tree by applying Algorithm 2. What follows, the extended strategy function for
the vertices of a layer component $L$ is calculated only after it is already
defined for all vertices below the component. Moreover, since we use a
structured $f$, only its values assigned to the roots of the layer components
below $L$ are important when calculating $f$ for the vertices of $L$.

1 $T\leftarrow$ a rooted rounding of $T$

2 for each layer component $L$ in bottom-up fashion do

3 Apply Algorithm 2 to $L$

4

return $f$

Algorithm 1 (input: tree $T$ with up-monotonic cost function; output: an
extended strategy function $f$ calculated for $T$)

Given a layer component $L$, Algorithm 2 iterates over the vertices of $L$ in
a depth-first, postorder fashion. Suppose that a structured extended strategy
function $f$ is defined on all vertices below $L$ and that $f$ is aligned to
$\omega(L)$ at all roots of layer components directly below $L$. To calculate
$f$ for the vertices of $L$, we first calculate the strategy function
$f^{\prime}$ for each vertex of $L$ and then obtain $f$ from $f^{\prime}$
using the formula: $f(u)=[f^{\prime}(u)\omega(L),(f^{\prime}(u)+1)\omega(L))$,
where $u\in V(L)$. (Recall that this is a conversion that takes us from the
integer-valued strategy function $f^{\prime}$ to the interval-valued extended
strategy function.) To provide an applicable input for the vertex extension
operator at the leaves of $L$, for each child $u\in V(L^{\prime})$ of such
leaf, we calculate the integer $f^{\prime}(u)=\frac{b}{\omega(L^{\prime})}$
that is derived from the extended strategy function at $u$, i.e. from
$f(u)=[a,b)$. Note that since our decision trees are structured, the
visibility sequence corresponding to each root of a layer component below $L$
(which includes $u$) consists of only one value, the one that equals the
strategy function at the root. What follows, deriving the value of
$f^{\prime}$ only for the roots of the layer components directly below $L$ is
sufficient to create a valid input for the vertex extension operator. In other
words, we make these preparations to use the operator and the corresponding
method from [38]. Once each vertex $v\in V(L)$ obtains the corresponding
extended strategy function $f(v)$, we apply for the root of $L$ the
structuring operator followed by the cost scaling operator. This will close
the entire ‘cycle’ of processing one layer component.

1

2for each root $v$ of a layer component directly below $L$ do

3 $f^{\prime}(v)\leftarrow\frac{b}{\omega(L)}$, where $b$ is the right
endpoint of the interval $f(v)$

4

5 for each $u\in V(L)$ in a postorder fashion do

6 Obtain $f^{\prime}(u)$ by applying the vertex extension operator to $v$

7 $f(u)\leftarrow$ the interval derived from $f^{\prime}(u)$, see Section 4

8

9 if the root $v$ of $L$ is not the root of $T$ then

10 Update $f(v)$ by applying the structuring operator to $v$

11 Update $f(v)$ by applying the cost scaling operator to $v$

12

Algorithm 2 (input: layer component $L$). Let $f$ be an extended strategy
function defined for all descendants of vertices in $L$ that do not belong to
$L$.

###  6.1 Analysis

Lemma 6.1 characterizes the interval of the extended strategy function that
Algorithm 2 assigns to the root of a layer component.

######  Lemma 6.1.

Consider a layer component $L$ of $T=(V,E,\omega)$ and a structured extended
strategy function $f$ defined on the vertices below $L$. Let the roots of the
layer components directly below $L$ be aligned to $\omega(L)$. Suppose that
the values of $f$ over $V(L)$ are obtained by a call to procedure
ProcessComponent(L,f). We have that $f$ is a structured extended strategy
function on $V(T_{r(L)})$, and the lowest possible interval $I$, such that
$I>f(u)$, for each $u$ below $r(L)$, is assigned to $r(L)$.

###### Proof.

Due to the alignment of $f$ at the roots of the components directly below $L$,
the strategy function $f^{\prime}$ derived from $f$ for these roots is
consistent with the query costs in $L$. That is, the construction of
$f^{\prime}$ done at the beginning of the procedure gives an integer-valued
strategy function. Since $f$ is structured, among all vertices below $L$, the
extension operator correctly needs to consider only the values of $f^{\prime}$
at the roots of components directly below $L$.

By Lemma 2.8, the visibility sequence calculated for the root of $L$ is
(lexicographically) minimized among all possible valid assignments of
$f^{\prime}$. Hence in particular, the value of $\max\\{f^{\prime}(v)\;|\;v\in
V(T_{r(L)})\\}$ is minimized. It follows that if there exists such an optimal
assignment of $f^{\prime}$ that is structured, then this $f^{\prime}$ is
calculated by the procedure is structured and consequently the $f$ obtained
from $f^{\prime}$ is minimal and structured. If there exists no optimal
assignments of $f^{\prime}$ over $V(L)$ that is structured, the structuring
operator modifies $f$ and assigns to $r(L)$ the lowest interval that is
greater than $f(u)$ for any $u$ below $r(L)$. ∎

It follows from Lemma 6.1 and Observation 4.2 that given an extended strategy
function $f$ fixed below a layer component $L$, Algorithm 1 extends $f$ to the
vertices of $L$ in such a way that the interval assigned to $r(L)$ is not
higher than the optimal interval (assuming that $f$ is fixed below $L$)
incremented by an additive factor $\omega(L^{\prime})-\omega(L)$, where
$L^{\prime}$ is a layer component directly above $L$. If $L$ is the top
component, the structuring transform is not applied and the additional cost is
not incurred.

We now formulate a technical Lemma 6.2 that helps analyze the strategy
generated by Algorithm 1.

######  Lemma 6.2.

Let $T=(V,E,\omega)$ be a tree with a up-monotonic and rounded cost function.
We denote by $f_{opt}$ an optimal structured extended strategy function on
$V(T)$. Let $L$ be a layer component of $T$ with $k$ layer components $L_{j}$,
$1\leq j\leq k$, directly below $L$. Let $v_{j}=r(L_{j}),1\leq j\leq k$. We
define $f^{\prime}$ as a function defined on $V(T)$ such that for all vertices
below any $v_{j}$, $f^{\prime}$ is equal to $f_{opt}$, while for the vertices
$v_{j}$ and above, $f^{\prime}$ is equal to $f_{opt}+\omega(L)$. It holds that
$f^{\prime}$ is a structured extended strategy function on $V(T)$.

###### Proof.

We first show that $f^{\prime}$ is an extended strategy function. We need to
show that for any pair $x,y\in V(T)$, $x\neq y$, if
$f^{\prime}(x)=f^{\prime}(y)$, then there is a vertex $z\in V(T)$ separating
$x,y$ such that $f^{\prime}(z)>f^{\prime}(x)$. (See Definition 2.5.)

We analyze the following cases with respect to the locations of the vertices
$x$ and $y$. In all cases we assume that $x\neq y$,
$f^{\prime}(x)=f^{\prime}(y)$, and $z$ is the vertex separating $x$ and $y$
according to $f^{\prime}$.

  * •

$x\in V(L_{i})$, $y\in V(L_{j})$ and $i=j$.

Let $v=r(L_{i})$. Because $f_{opt}$ is structured, $f^{\prime}$ is also
structured within the subtree $T_{v}$, since it assigns $v$ a higher interval
than $f_{opt}$ and $f^{\prime}$ is otherwise identical to $f_{opt}$. What
follows, because $f^{\prime}$ is structured and we assumed
$f^{\prime}(x)=f^{\prime}(y)$, we have that $x\neq v$ and $y\neq v$.

Consider the $f_{opt}$ as defined on all vertices of $L_{i}$. Because $x,y\in
V(L_{i})$, we have $z\in V(L_{i})$. If $z\neq v$, then
$f^{\prime}(z)=f_{opt}(z)>f_{opt}(x)=f^{\prime}(x)$, where the last equation
holds because $x\neq v$. If $z=v$, we also have $f^{\prime}(z)>f^{\prime}(x)$,
because $f^{\prime}$ is structured in $T_{v}$.

  * •

$x\in V(L_{i})$, $y\in V(L_{j})$ and $i\neq j$.

Because $f^{\prime}$ is structured in $L_{i}$, we have $z=r(L_{i})$.

  * •

Both $x$ and $y$ belong to $V(L)$.

Because $f_{opt}$ is an extended strategy function in $L$, there is a $z\in
V(L)$ such that $f_{opt}(z)>f_{opt}(x)$. Then, by adding $\omega(L)$ to both
sides of the inequality one obtains $f^{\prime}(z)>f^{\prime}(x)$.

  * •

$x\in V(L_{i})$ for some $i$ and $y\in V(L)$.

If $x\neq r(L_{i})$ then $z=r(L_{i})$, because $f^{\prime}$ is structured in
$L_{i}$.

Otherwise, both $x$ and $y$ are in the subtree $T[V(L)\cup\\{x\\}]$. Recall
that in this subtree $f^{\prime}$ is derived from $f_{opt}$ by adding a
constant offset, which gives an extended strategy function.

To show that $f^{\prime}$ is structured in the remaining cases, we observe
that for all vertices above $L$, $f^{\prime}$ is derived from the structured
$f_{opt}$ by shifting the assigned intervals by a positive offset, which does
not change the structural property of the layer components’ roots. ∎

######  Lemma 6.3.

The cost of the decision tree generated by Algorithm 1 is at most 2 times
greater than the cost of an optimal structured decision tree.

###### Proof.

The proof is by induction, bottom-up over the layer components of the input
tree. Take a tree $T=(V,E,\omega)$ with an up-monotonic and rounded cost
function. We denote by $c(i),1\leq i\leq l$, the query cost to a vertex in the
$i-th$ layer, where the layers are ordered according to their cost of query
and $l$ is the number of layers in $T$. Let $f_{opt}$ be an optimal
(structured) extended strategy function and $f_{alg}$ be the extended strategy
function generated by Algorithm 1. We denote by $z(v)$ the cost of querying
the parent of $v$ or the cost of $v$ itself if there is no vertex above $v$,
i.e. when $v$ is the root of $T$.

We want to prove the following induction claim. For any layer component $L$ it
holds $f_{alg}(v)\leq f_{opt}(v)+z(v)$, where $v=r(L)$.

The cost of the decision tree generated by $f_{alg}$ is equal to the supremum
of $f_{alg}(r(T))$. Since the cost of a single query to the top layer is not
more than the cost of an optimal structured decision tree, the lemma follows
from the induction claim applied to the top layer component.

Let $L$ be a bottom layer component. Based on Lemma 6.1 we know that by
applying the vertex extension and structuring operators, Algorithm 1 generates
an optimal structured assignment of the extended strategy function to the
vertices of $L$. In a case where $L$ is also the top component (which is the
trivial case of $T$ being a single layer component) we have $f_{alg}$ is
optimal and the induction claim holds. Otherwise, the cost scaling operator
extends the interval assigned to $r(L)$, increasing the cost of $L$ by (at
most) an additive factor of $c(2)-c(1)$ over the optimal cost. Since the added
factor is less than $z(r(L))$, the induction claim holds for the bottom layer
component $L$.

Let $L$ be a layer component from the $i$-th layer, with $k$ layer components
$L_{j}$, $1\leq j\leq k$, directly below $L$. We denote the roots of the layer
components $L_{j}$ by $v_{j}$. Consider a strategy function $f^{\prime}$ which
is defined as in Lemma 6.2, that is for all vertices below any $v_{j}$,
$f^{\prime}$ is equal to $f_{opt}$, while for vertices $v_{j}$ and all
vertices above, $f^{\prime}$ is equal to $f_{opt}+\omega(L)$. Lemma 6.2
implies that $f^{\prime}$ is a structured extended strategy function on
$V(T)$.

From the induction hypothesis we have that for any $v_{j}$,
$f_{alg}(v_{j})\leq f_{opt}(v_{j})+z(v_{j})=f_{opt}(v_{j})+\omega(L)$.
According to Lemma 6.1 and Observation 4.2, Algorithm 1 assigns intervals to
the vertices of $L$ such that the interval assigned to the root of $L$ is the
lowest possible (when $L$ is the top component), or the lowest possible
interval incremented by a positive offset of $\omega(L^{\prime})-\omega(L)$,
where $L^{\prime}$ is the layer component directly above $L$. If we sum up the
additive increments due to cost scaling in all layer components below $L$, we
obtain $\sum_{i<l}c(i)<c(l)=z(v)$ (recall that $c(i)$’s are powers of $2$).
Thus, $f_{alg}(v)\leq f_{opt}(v)+z(v)$. ∎

By combining Lemmas 2.4, 3.2, and 6.3 we obtain that Algorithm 1 generates a
solution for the binary search problem with a cost at most $8$ times greater
than that of an optimal solution. We note that Algorithm 1 maintains the main
structure of the linear time algorithm from [38] (a single bottom-up pass over
vertices of the tree.) Our method extends the state-of-the-art algorithm by
adding a fixed number of $\mathcal{O}{1}$ steps, computed when visiting
vertices during the bottom-up traversal. See Algorithm 2. What follows,
Algorithm 1 also runs in linear time. This proves Theorem 1.1.

##  7 The algorithm for down-monotonic cost functions

In this section, we describe and analyze the algorithm providing Theorem 1.2.
To construct an interval-based extended strategy function $f$, our procedure
adapts the greedy linear-time algorithm for searching in trees with uniform
query costs [38]. Let $T=(V,E,\omega)$ be a rooted tree, such that $\omega$ is
rounded and down-monotonic. Recall that the root must be one of the vertices
of minimal weight.

In our algorithm that takes $T$ as input, the intervals that $f$ assigns to
the vertices are calculated in a bottom-up fashion. Consider a vertex $v\in
V(T)$ with $k>0$ children $v_{1},\ldots,v_{k}$ so that $f$ is defined on all
descendants of $v$. For each $v_{i}$, we denote the extended visibility
sequence derived from $f$ restricted to $T_{v_{i}}$ by $S(v_{i})$. Let
$\mathcal{I}$ be the set of all intervals $I$ that belong to any $S(v_{i})$,
such that there exists an interval $I^{\prime}\in S(v_{j})$, $i\neq j$, where
$I\cap I^{\prime}\neq\emptyset$. If $\mathcal{I}\neq\emptyset$, let $I_{M}$ be
the maximal interval in $\mathcal{I}$. If $\mathcal{I}=\emptyset$, then let
$I_{M}=[-1,0)$. The minimal interval $I$ with endpoints being multiples of
$\omega(v)$, such that $I>I_{M}$, $|I|=\omega(v)$ and $I\cap
I^{\prime}=\emptyset$ for each $I^{\prime}\in S(v_{1})\cup\cdots\cup S(v_{k})$
is called the _greedy interval_ for $v$. In case when $v$ has no children the
_greedy interval_ for $v$ is $[0,\omega(v))$.

The algorithm for a rounded down-monotonic cost function simply assigns the
greedy interval for each vertex, once such intervals are constructed for the
children. The pseudo-code is shown as Algorithm 3.

1 Compute a rooted rounding of the input tree.

2 for each vertex $v$ in a bottom-up fashion do

3 Compute the greedy interval $I^{\prime}$ for $v$ and set $f(v)\leftarrow
I^{\prime}$.

return the search strategy that corresponds to $f$.

Algorithm 3 (input: a tree with down-monotonic cost function).

###  7.1 Analysis

In order to prove the correctness and efficiency, we will now introduce
concepts that allow to express the extended visibility sequences used in our
methodology in terms of the vertex extension operator over integer-valued
sequences that were developed for searching in unweighted trees [38].

######  Definition 7.1.

Let $S(v)$ be an extended visibility sequence for some $v\in V(T)$. Take a
$d\in\mathbb{N}$ that divides $\omega(v)$. We say that the visibility sequence
$S^{d}(v)$ is _corresponding to_ $S(v)$ with _granularity_ $d$ if and only if
it lists in decreasing order all values obtained in the following way. For
every interval $[a,b)\in S(v)$, add to $S^{d}(v)$ the values $\frac{a}{d}+i$
for each $i\in\\{0,\ldots,n-1\\}$, where $n=\frac{b-a}{d}$.

Our further analysis will leverage a key property of aligned extended strategy
functions, expressed by Observation 7.2, which is later used in Lemma 7.3.

######  Observation 7.2.

Let $S_{1}$ and $S_{2}$ be extended visibility sequences such that there
exists a $d\in\mathbb{N}$ that divides the endpoint of each interval in both
$S_{1}$ and $S_{2}$. We have that $S_{1}<_{l}S_{2}$ if and only if
$S^{d}_{1}<_{l}S^{d}_{2}$. ∎

An extended visibility sequence $S(v)$ of a vertex $v$ is _lexicographically
minimal_ if:

  * •

there exists an extended strategy function $f$ defined on $T_{v}$ such that
$S(v)$ is derived from $f$, and

  * •

there exists no extended strategy function $f^{\prime}$ defined on $T_{v}$,
such that $S^{\prime}(v)<_{l}S(v)$, where $S^{\prime}(v)$ is the extended
visibility sequence for $v$ derived from $f^{\prime}$.

The following Lemma 7.3 serves as an induction step, which when applied
bottom-up over the input tree, shows that Algorithm 3 indeed returns an
optimal strategy.

######  Lemma 7.3.

Consider a tree $T=(V,E,\omega)$, with rounded and down-monotonic $\omega$. If
the extended visibility sequence of each child of some vertex $v$ is
lexicographically minimal, then the greedy interval for $v$ is also
lexicographically minimal.

###### Proof.

Let $v_{1},\ldots,v_{k}$ be the children of $v$. Let $f$, defined for the
subtrees $T_{v_{1}},\ldots,T_{v_{k}}$, be such that for each
$i\in\\{1,\ldots,k\\}$ the lexicographically minimal sequence $S(v_{i})$ is
derived from $f$. Take extended visibility sequences $\tilde{S}(v_{i})$ for
each $i\in\\{1,\ldots,k\\}$ that are derived from an arbitrary extended
strategy function. By assumption, for each child $v_{i}$, we have that
$S(v_{i})\leq_{l}\tilde{S}(v_{i})$. Based on Observation 7.2, we also have
that

$S^{d_{i}}(v_{i})\leq_{l}\tilde{S}^{d_{i}}(v_{i}),$ (2)

where $d_{i}=\omega(v_{i})$ for each $i$. Note that the $d_{i}$ may be
different for different children $v_{i}$.

We apply the vertex extension operator (see Definition 2.7) for $v$ using the
sequences $\tilde{S}^{d_{i}}(v_{i})$. Since the vertex extension operator is
minimizing [38], it assigns to $v$ the lexicographically minimal sequence
$\tilde{S}^{d}(v)$ available for $v$, out of all valid visibility sequences,
given the sequences assigned to the children. Note that since $\omega$ is
rounded and down-monotonic, we have that $d$ divides $d_{i}$ for each
$i\in\\{1,\ldots,k\\}$. For each $i$, we have that (2) implies
$S^{d}(v_{i})\leq_{l}\tilde{S}^{d}(v_{i})$. Intuitively, we may switch from
the granularities $d_{i}$ to $d$ preserving the ordering of sequences. On the
other hand, the vertex extension operator is monotone [38] and when applied on
the sequences $S^{d_{i}}(v_{i})$, the resulting sequence $S^{d}(v)$ satisfies
$S^{d}(v)\leq_{l}\tilde{S}^{d}(v)$. Consider extending $f$ to $T_{v}$ by
assigning to $v$ the greedy interval to $v$. By the definition, the extended
visibility sequence $S(v)$ derived from such $f$ is such that $S^{d}(v)$
corresponds to $S(v)$. This proves that $S(v)$ is lexicographically minimal as
required. ∎

By induction over the subtrees of $T$, with the induction claim formulated by
Lemma 7.3, one obtains that the search strategy returned by Algorithm 3 is
optimal for the rounding $T$ of the input tree $T^{\prime}$. On the other
hand, we have $OPT(T)\leq 2\cdot OPT(T^{\prime})$. This implies that the
algorithm is $2$-approximate for an arbitrary input tree. Since the tree has
$n$ vertices, the lexicographically minimal sequence for each vertex $v$ has
$\mathcal{O}(n)$ intervals. Hence, the computation of the greedy interval
takes $\mathcal{O}(n)$ time, as well as any other list manipulation task,
proving that the algorithm has polynomial running time. This completes the
proof of Theorem 1.2.

##  8 The algorithm for $k$-monotonic cost functions

Consider a partitioning of a rounded tree $T=(V,E,\omega)$ into subtrees
$T_{1},\ldots,T_{l}$ as in the definition of a $k$-monotonic cost function
(cf. Section 1.5). The subtree $T_{i}$ that contains the root of $T$ is called
the _root subtree_. In the case of Algorithm 3, our methodology made it easier
to frame it as a procedure that is computing an extended strategy function.
This then allows to get the corresponding search algorithm as explained in
Section 2. However, with the tools we have it is more natural to present a
procedure (cf. Algorithm 4) that gives Theorem 1.3 as an adaptive process that
instead of outputting a search strategy, actually performs the adaptive search
and returns the target.

1 Let $T^{\prime}$ be the root subtree of the rounding of the input tree.

2 Compute a search strategy $\mathcal{A}$ for $T^{\prime}$.

3 Execute $\mathcal{A}$.

4 if the target $t$ is in $T^{\prime}$ then

5 return $t$.

6 else

7 Let $v$ be the child of a leaf of $T^{\prime}$ such that $T_{v}$ contains
the target.

8 Call recursively Algorithm 4 with input $T_{v}$.

Algorithm 4 (input: a tree $T$ with $k$-monotonic cost function; output: the
target).

To compute the search strategy in line 4, if $T^{\prime}$ is down-monotonic,
use the $2$-approximation Algorithm 3, otherwise use the $8$-approximation
Algorithm 1. If the target $t$ is not in $T^{\prime}$, then let $v$ be the
first vertex outside of $T^{\prime}$ on the path from the root of $T$ to $t$.
Note that all queries performed within $T^{\prime}$ are then pointing towards
$v$ in their replies. The same holds during a query to the parent of $v$,
which is a leaf of $T^{\prime}$. Thus, the vertex $v$ can be correctly
selected in line 4. The depth of the recursion is at most $k$ and each
strategy execution in line 4 introduces a cost of at most $8\cdot
OPT(T^{\prime})\leq 8\cdot OPT(T)$. The recursion correctly ends when
$T^{\prime}$ is such that no vertex of $T^{\prime}$ has a child that does not
belong to $T^{\prime}$ (i.e., all leaves in $T^{\prime}$ are also leaves in
$T$). This gives Theorem 1.3.

##  9 The NP-completeness

It has been shown in [10] that the edge variant of binary search is NP-
complete already for specific small-diameter trees. We will use this fact to
argue that vertex search with $k$-monotonic cost functions is not FPT with
respect to $k$.

The edge search problem considers as an input an edge-weighted tree
$T^{\prime}=(V,E,c)$, where $c$ attributes each edge with the cost of the
query. For an arbitrary search target $t\in V(T^{\prime})$, a query to an edge
$e\in E(T^{\prime})$ incurs the cost of $c(e)$ and learns which one of the two
components in $T^{\prime}-e$ contains $t$. For a given input tree, similarly
as in the vertex search, the goal of the algorithm is to obtain a search
strategy that has minimal total cost in the worst case. Note that this problem
can be equivalently defined as performing vertex search in the line graph of
$T^{\prime}$.

Following the description provided in [14], we formulate Lemma 9.1, which
shows a connection between the two problems. First, for each tree $T^{\prime}$
we define its _subdivision_ $T=(V,E,\omega)$ as follows. Let $M=1+\sum_{e\in
E(T^{\prime})}c(e)$ exceed the weight of all edges in $T^{\prime}$. For each
$e\in E(T^{\prime})$ introduce a vertex $v(e)$ with weight
$\omega(v(e))=c(e)$. Then, $V(T)=V(T^{\prime})\cup\\{v(e)\colon e\in
E(T^{\prime})\\}$, $E(T)=\\{\\{x,v(e)\\},\\{v(e),y\\}\colon e=\\{x,y\\}\in
E(T^{\prime})\\}$, and $\omega(x)=M$ for each $x\in V(T^{\prime})$. In other
words, we obtain $T$ by putting the weight $M$ on each vertex of $T^{\prime}$
and subdividing each edge $e$ so that the new vertex $v(e)$ that comes from
the subdivision of $e$ ‘inherits’ its weight from $e$. Informally, the idea
behind this construction is that when performing a vertex search on $T$, one
should never query any vertex $x$ in $V(T^{\prime})$ due to the large weights.
Instead, in order to learn whether $x$ is the target in $T$, it is favorable
to query all of its neighbors.

######  Lemma 9.1 ([14]).

For each tree $T^{\prime}$, the edge search cost of $T^{\prime}$ equals
$OPT(T)$.

###### Proof.

Consider algorithm $\mathcal{A}$ for vertex search in $T$ based on the edge
search algorithm on $T^{\prime}$. $\mathcal{A}$ queries only the _old_
vertices. If the queried vertex is the target _A_ stops. Otherwise,
$\mathcal{A}$ continues in the subgraph that can still contain the target,
until either the target vertex is queried or the subtree is reduced to a
single vertex.

  * •

If target is one of the old/original vertices, it will be found by reducing
$T$ to a single vertex - the search target. The cost in worst case is OPT(T’).

  * •

If target vertex is one of the new vertices, $\mathcal{A}$ will continue the
search until it queries the search target. Note that every edge of T’ is
queried when searching for some target vertex in T’. The cost of searching
such target in worst case is OPT(T’).

∎

It has been shown in [10] that the edge search is (strongly) NP-complete in
the class of spiders of diameter at most $6$. For each such spider
$T^{\prime}$, the diameter of its subdivision $T$ equals $12$, and the
corresponding cost function $\omega$ is $4$-monotonic. This proves Theorem
1.4.

##  10 Conclusions

Our first remark is on a possible complexity gap with respect to $k$. It is
not known whether the problem for $1$-monotonic cost functions is NP-complete
(cf. [20]). Hence an open problem remains whether the value of $k=4$ in
Theorem 1.4 is in fact tight. We conjecture that the problem is NP-complete
for a $k<4$. Our conjecture is supported by the fact that we obtained the
constant $k=4$ basically via a ‘black-box’ transformation from the edge search
[10]. Thus, a more refined reduction might provide the right threshold for
$k$.

In a wider context, our work is en route to a search for a constant factor
approximation algorithm for an arbitrary cost function in trees. Our choice of
looking at $k$-monotonic cost functions may be seen as the problem
parametrization with respect to $k$. However, it is interesting if other
parametrization methods are also natural and algorithmically promising.

We recall a related tree search problem, called _edge search_ , in which one
performs queries on edges: each reply provides information which endpoint of
the queried edge is closer to the target [3]. One can similarly define for
example an up-monotonic cost function $\omega\colon
E(T)\rightarrow\mathbb{R_{+}}$ for the edge search by requiring that there
exists a choice for the root $r$ so that for any two edges $\\{x,y\\}$ and
$\\{y,z\\}$, if $x$ is closer to $r$ than $y$, then
$\omega(\\{x,y\\})\geq\omega(\\{y,z\\})$. We have outlined some evidence that
for unweighted trees, the edge search has been more challenging to analyze
than the vertex search, both when it comes to finding good upper bounds (see
[42] vs [16, 23, 33]) and optimal algorithms (see [42] vs [38, 32]). In view
of the relation between the two problems in their weighted variants (see
Section 9) it may be possible that the above does not carry out to this case.
Hence, a fruitful path to get algorithmic progress for the weighted vertex
search problem is to first develop new techniques for the weighted edge
search.

Also, we repeat the previously mentioned interesting and challenging open
question whether a constant-factor approximation is possible for the vertex
search in trees with general weight functions.

## References

  * [1] Alok Aggarwal, Bowen Alpern, Ashok K. Chandra, and Marc Snir.  A model for hierarchical memory.  In STOC 1987, pages 305–314, 1987.  doi:10.1145/28395.28428.
  * [2] Haris Angelidakis.  Shortest path queries, graph partitioning and covering problems in worst and beyond worst case settings.  CoRR, abs/1807.09389, 2018.  arXiv:1807.09389.
  * [3] Yosi Ben-Asher, Eitan Farchi, and Ilan Newman.  Optimal search in trees.  SIAM J. Comput., 28(6):2090–2102, 1999.  doi:10.1137/S009753979731858X.
  * [4] Benjamin Aram Berendsohn and László Kozma.  Splay trees on trees.  In SODA 2022, pages 1875–1900, 2022.  doi:10.1137/1.9781611977073.75.
  * [5] Guy E. Blelloch and Magdalen Dobson.  The geometry of tree-based sorting.  In ICALP 2023, pages 26:1–26:19, 2023.  doi:10.4230/LIPICS.ICALP.2023.26.
  * [6] Lucas Boczkowski, Uriel Feige, Amos Korman, and Yoav Rodeh.  Navigating in trees with permanently noisy advice.  ACM Trans. Algorithms, 17(2):15:1–15:27, 2021.  doi:10.1145/3448305.
  * [7] Hans L. Bodlaender, John R. Gilbert, Ton Kloks, and Hjálmtyr Hafsteinsson.  Approximating treewidth, pathwidth, and minimum elimination tree height.  In WG 1991, pages 1–12, 1991.  doi:10.1007/3-540-55121-2\\_1.
  * [8] Piotr Borowiecki, Dariusz Dereniowski, and Dorota Osula.  The complexity of bicriteria tree-depth.  In FCT 2021, pages 100–113, 2021.  doi:10.1007/978-3-030-86593-1\\_7.
  * [9] Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Caio Dias Valentim.  Binary identification problems for weighted trees.  In WADS 2011, pages 255–266, 2011.  doi:10.1007/978-3-642-22300-6\\_22.
  * [10] Ferdinando Cicalese, Balázs Keszegh, Bernard Lidický, Dömötör Pálvölgyi, and Tomás Valla.  On the tree search problem with non-uniform costs.  Theor. Comput. Sci., 647:22–32, 2016.  doi:10.1016/j.tcs.2016.07.019.
  * [11] Argyrios Deligkas, George B. Mertzios, and Paul G. Spirakis.  Binary search in graphs revisited.  Algorithmica, 81(5):1757–1780, 2019.  doi:10.1007/S00453-018-0501-Y.
  * [12] Dariusz Dereniowski.  Edge ranking of weighted trees.  Discret. Appl. Math., 154(8):1198–1209, 2006.  doi:10.1016/j.dam.2005.11.005.
  * [13] Dariusz Dereniowski.  Edge ranking and searching in partial orders.  Discret. Appl. Math., 156(13):2493–2500, 2008.  doi:10.1016/j.dam.2008.03.007.
  * [14] Dariusz Dereniowski, Adrian Kosowski, Przemyslaw Uznanski, and Mengchuan Zou.  Approximation strategies for generalized binary search in weighted trees.  In ICALP 2017, pages 84:1–84:14, 2017.  doi:10.4230/LIPIcs.ICALP.2017.84.
  * [15] Dariusz Dereniowski and Marek Kubale.  Cholesky factorization of matrices in parallel and ranking of graphs.  In PPAM 2003, pages 985–992, 2003.  doi:10.1007/978-3-540-24669-5\\_127.
  * [16] Dariusz Dereniowski and Marek Kubale.  Efficient parallel query processing by graph ranking.  Fundam. Informaticae, 69(3):273–285, 2006.
  * [17] Dariusz Dereniowski, Aleksander Lukasiewicz, and Przemyslaw Uznanski.  An efficient noisy binary search in graphs via median approximation.  In IWOCA 2021, pages 265–281, 2021.  doi:10.1007/978-3-030-79987-8\\_19.
  * [18] Dariusz Dereniowski and Adam Nadolski.  Vertex rankings of chordal graphs and weighted trees.  Inf. Process. Lett., 98(3):96–100, 2006.  doi:10.1016/j.ipl.2005.12.006.
  * [19] Dariusz Dereniowski, Stefan Tiegel, Przemyslaw Uznanski, and Daniel Wolleb-Graf.  A framework for searching in graphs in the presence of errors.  In SOSA@SODA 2019, pages 4:1–4:17, 2019.  doi:10.4230/OASIcs.SOSA.2019.4.
  * [20] Dariusz Dereniowski and Izajasz P. Wrosz.  Constant-factor approximation algorithm for binary search in trees with monotonic query times.  In MFCS 2022, pages 42:1–42:15, 2022.  doi:10.4230/LIPIcs.MFCS.2022.42.
  * [21] Ehsan Emamjomeh-Zadeh and David Kempe.  A general framework for robust interactive learning.  In NIPS 2017, pages 7082–7091, 2017.
  * [22] Ehsan Emamjomeh-Zadeh, David Kempe, Mohammad Mahdian, and Robert E. Schapire.  Interactive learning of a dynamic structure.  In ALT 2020, pages 277–296, 2020.
  * [23] Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal.  Deterministic and probabilistic binary search in graphs.  In STOC 2016, pages 519–532, 2016.  doi:10.1145/2897518.2897656.
  * [24] Archontia C. Giannopoulou, Paul Hunter, and Dimitrios M. Thilikos.  Lifo-search: A min-max theorem and a searching game for cycle-rank and tree-depth.  Discrete Applied Mathematics, 160(15):2089–2097, 2012.  doi:10.1016/j.dam.2012.03.015.
  * [25] Ryusuke Hohzaki.  Search games: Literature and survey.  Journal of the Operations Research Society of Japan, 59(1):1–34, 2016.  doi:10.15807/jorsj.59.1.
  * [26] Ananth V. Iyer, H. Donald Ratliff, and Gopalakrishnan Vijayan.  Optimal node ranking of trees.  Inf. Process. Lett., 28(5):225–229, 1988.  doi:10.1016/0020-0190(88)90194-9.
  * [27] Ananth V. Iyer, H. Donald Ratliff, and Gopalakrishnan Vijayan.  On an edge ranking problem of trees and graphs.  Discret. Appl. Math., 30(1):43–52, 1991.  doi:10.1016/0166-218X(91)90012-L.
  * [28] Meir Katchalski, William McCuaig, and Suzanne M. Seager.  Ordered colourings.  Discret. Math., 142(1-3):141–154, 1995.  doi:10.1016/0012-365X(93)E0216-Q.
  * [29] Donald E. Knuth.  The Art of Computer Programming, Volume III: Sorting and Searching.  Addison-Wesley, 1973.
  * [30] Eduardo Sany Laber, Ruy Luiz Milidiú, and Artur Alves Pessoa.  On binary searching with nonuniform costs.  SIAM J. Comput., 31(4):1022–1047, 2002.  doi:10.1137/S0097539700381991.
  * [31] Eduardo Sany Laber and Marco Molinaro.  An approximation algorithm for binary searching in trees.  Algorithmica, 59(4):601–620, 2011.  doi:10.1007/s00453-009-9325-0.
  * [32] Tak Wah Lam and Fung Ling Yue.  Optimal edge ranking of trees in linear time.  In SODA 1998, pages 436–445, 1998.
  * [33] Kazuhisa Makino, Yushi Uno, and Toshihide Ibaraki.  On minimum edge ranking spanning trees.  J. Algorithms, 38(2):411–437, 2001.  doi:10.1006/jagm.2000.1143.
  * [34] Keizo Miyata, Shigeru Masuyama, Shin-ichi Nakayama, and Liang Zhao.  Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem.  Discret. Appl. Math., 154(16):2402–2410, 2006.  doi:10.1016/j.dam.2006.04.016.
  * [35] Shay Mozes, Krzysztof Onak, and Oren Weimann.  Finding an optimal tree searching strategy in linear time.  In SODA 2008, pages 1096–1105, 2008.
  * [36] Gonzalo Navarro, Ricardo A. Baeza-Yates, Eduardo F. Barbosa, Nivio Ziviani, and Walter Cunto.  Binary searching with nonuniform costs and its application to text retrieval.  Algorithmica, 27(2):145–169, 2000.  doi:10.1007/s004530010010.
  * [37] Jaroslav Nešetřil and Patrice Ossona de Mendez.  Tree-depth, subgraph coloring and homomorphism bounds.  Eur. J. Comb., 27(6):1022–1041, 2006.  doi:10.1016/j.ejc.2005.01.010.
  * [38] Krzysztof Onak and Pawel Parys.  Generalization of binary search: Searching in trees and forest-like partial orders.  In FOCS 2006, pages 379–388, 2006.  doi:10.1109/FOCS.2006.32.
  * [39] Andrzej Pelc.  Searching games with errors — fifty years of coping with liars.  Theor. Comput. Sci., 270(1-2):71–109, 2002.  doi:10.1016/S0304-3975(01)00303-6.
  * [40] Stuart J. Russell and Peter Norvig.  Artificial Intelligence - A Modern Approach, Third International Edition.  Pearson Education, 2010.
  * [41] Sherif Sakr, Angela Bonifati, Hannes Voigt, Alexandru Iosup, Khaled Ammar, Renzo Angles, Walid G. Aref, Marcelo Arenas, Maciej Besta, Peter A. Boncz, Khuzaima Daudjee, Emanuele Della Valle, Stefania Dumbrava, Olaf Hartig, Bernhard Haslhofer, Tim Hegeman, Jan Hidders, Katja Hose, Adriana Iamnitchi, Vasiliki Kalavri, Hugo Kapp, Wim Martens, M. Tamer Özsu, Eric Peukert, Stefan Plantikow, Mohamed Ragab, Matei Ripeanu, Semih Salihoglu, Christian Schulz, Petra Selmer, Juan F. Sequeda, Joshua Shinavier, Gábor Szárnyas, Riccardo Tommasini, Antonino Tumeo, Alexandru Uta, Ana Lucia Varbanescu, Hsiang-Yun Wu, Nikolay Yakovets, Da Yan, and Eiko Yoneki.  The future is big graphs: a community view on graph processing systems.  Commun. ACM, 64(9):62–71, 2021.  doi:10.1145/3434642.
  * [42] Alejandro A. Schäffer.  Optimal node ranking of trees in linear time.  Inf. Process. Lett., 33(2):91–96, 1989.  doi:10.1016/0020-0190(89)90161-0.
  * [43] Arunabha Sen, Haiyong Deng, and Sumanta Guha.  On a graph partition problem with application to VLSI layout.  Inf. Process. Lett., 43(2):87–94, 1992.  doi:10.1016/0020-0190(92)90017-P.
  * [44] Xiao Zhou, Mohammod Abul Kashem, and Takao Nishizeki.  Generalized edge-ranking of trees (extended abstract).  In WG 1996, pages 390–404, 1996.  doi:10.1007/3-540-62559-3\\_31.
  * [45] Xiao Zhou, Nobuaki Nagai, and Takao Nishizeki.  Generalized vertex-rankings of trees.  Inf. Process. Lett., 56(6):321–328, 1995.  doi:10.1016/0020-0190(95)00172-7.