On the tree search problem with non-uniform costs

Thumbnail Image
Cicalese, Ferdinando
Keszegh, Balázs
Pálvölgyid, Dömötör
Valla, Tomáš
Major Professor
Committee Member
Journal Title
Journal ISSN
Volume Title
Lidicky, Bernard
Research Projects
Organizational Units
Organizational Unit
Welcome to the exciting world of mathematics at Iowa State University. From cracking codes to modeling the spread of diseases, our program offers something for everyone. With a wide range of courses and research opportunities, you will have the chance to delve deep into the world of mathematics and discover your own unique talents and interests. Whether you dream of working for a top tech company, teaching at a prestigious university, or pursuing cutting-edge research, join us and discover the limitless potential of mathematics at Iowa State University!
Journal Issue
Is Version Of

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.

Fri Jan 01 00:00:00 UTC 2016