On the tree search problem with non-uniform costs

DOI10.1016/J.TCS.2016.07.019zbMATH Open1350.68084arXiv1404.4504OpenAlexW2293258084MaRDI QIDQ306704FDOQ306704

Authors: Ferdinando Cicalese, Balázs Keszegh, Bernard Lidický, Dömötör Pálvölgyi, T. Valla 

Publication date: 1 September 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indexes, 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: given a tree $T$ where each edge has 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 tree of degree 3 or diameter 6. The best known approximation guarantee is the $O(logn/logloglogn)$-approximation algorithm of [Cicalese et al. TCS 2012]. 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(fraclognloglogn)$-approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-complete even when the input tree is a spider, i.e., at most one vertex has degree larger than 2.

Full work available at URL: https://arxiv.org/abs/1404.4504

Recommendations

• On the tree search problem with non-uniform costs
• On the complexity of searching in trees and partially ordered structures
• On the complexity of searching in trees: average-case minimization
• Improved approximation algorithms for the average-case tree searching problem
• Approximation strategies for generalized binary search in weighted trees

zbMATH Keywords

approximation algorithmtree search problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On an edge ranking problem of trees and graphs
• Edge ranking and searching in partial orders
• Title not available (Why is that?)
• The binary identification problem for weighted trees
• On the hardness of the minimum height decision tree problem
• Optimal edge ranking of trees in polynomial time
• Edge ranking of weighted trees
• On minimum edge ranking spanning trees
• Title not available (Why is that?)
• Searching ordered structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal Search in Trees

Cited In (11)

• On the tree search problem with non-uniform costs
• On binary searching with non-uniform costs
• Competitive Online Search Trees on Trees
• Partial order multiway search
• A pathfinding problem for search trees with unknown edge length
• Edge and pair queries-random graphs and complexity
• Cost-error relationships in A* tree-searching
• On the complexity of searching in trees and partially ordered structures
• On the complexity of searching in trees: average-case minimization
• The complexity of bicriteria tree-depth
• The complexity of bicriteria tree-depth

This page was built for publication: On the tree search problem with non-uniform costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306704)