Improved Approximation Algorithms for the Average-Case Tree Searching Problem

We study the following tree search problem: in a given tree T = (V , E) a vertex has been marked and we want to identify it. In order to locate the marked vertex, we can use edge queries. An edge query e asks in which of the two connected components of T \ e the marked vertex lies. The worst-case scenario where one is interested in minimizing the maximum number of queries is well understood, and linear time algorithms are known for finding an optimal search strategy. Here we study the more involved average-case analysis: A function w : V → R+ is given which measures the likelihood for a vertex to be the one marked, and we seek to determine the strategy (decision tree) that minimizes the weighted average number of queries. In a companion paper we prove that the above tree search problem is NP- complete even for the class of trees of bounded diameter or bounded degree. Here, we match this complexity result with a tight algorithmic analysis of the bounded degree instances. We show that any optimal strategy (i.e., one that minimizes the weighted average number of queries) performs at most O(Delta(T )(log |V | + log(w(T )/wmin))) queries in the worst case, where w(T ) is the sum of the likelihoods of the vertices of T , wmin is the minimum positive likelihood over the vertices of T and Delta(T ) is the maximum degree of T . We combine this result with a non-trivial exponential time algorithm to provide an FPTAS for trees with bounded degree. We also show that for unbounded instances a natural greedy strategy attains a 1.62-approximation, improv- ing upon the best known 14-approximation guarantee, previously provided by two of the authors