Campus Units


Document Type


Publication Version

Accepted Manuscript

Publication Date


Journal or Book Title

Theoretical Computer Science



First Page


Last Page





Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indices, as well as in hierarchy based knowledge representation. In this paper we focus on tree-like partial orders and consider the problem of identifying an initially unknown vertex in a tree by asking edge queries: an edge query e returns the component of T - e containing the vertex sought for, while incurring some known cost c(e). The Tree Search Problem with Non-Uniform Cost is the following: given a tree T on n vertices, each edge having an associated cost, construct a strategy that minimizes the total cost of the identification in the worst case.

Finding the strategy guaranteeing the minimum possible cost is an NP-complete problem already for input trees of degree 3 or diameter 6. The best known approximation guarantee was an O (log n/log log log n)-approximation algorithm of Cicalese et al. (2012) [4].

We improve upon the above results both from the algorithmic and the computational complexity point of view: We provide a novel algorithm that provides an O (log n/log log n)-approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-hard even when the input tree is a spider of diameter 6, i.e., at most one vertex has degree larger than 2.


This is a manuscript of an article published as Cicalese, Ferdinando, Balázs Keszegh, Bernard Lidický, Dömötör Pálvölgyi, and Tomáš Valla. "On the tree search problem with non-uniform costs." Theoretical Computer Science 647 (2016): 22-32. doi:10.1016/j.tcs.2016.07.019. Posted with permission.

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Copyright Owner

Elsevier B.V.



File Format


Published Version