Searching in trees with k-up-modular cost functions

2025/04/24 by Szyfelbein, Michał · 1 citation
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2

paper · doi:10.48550/arxiv.2504.17887

Abstract

Consider the following generalization of the classic binary search problem: a searcher is required to find a hidden vertex x in a tree T. To do so, they iteratively perform queries to an oracle, each about a chosen vertex v. After each such call, the oracle responds whether the target was found and if not, the searcher receives as a reply the connected component of T-v which contains x. Additionally, each vertex v may have a different query cost c(v). The goal is to find the optimal querying strategy which minimizes the worst case cost required to find x. The problem is known to be NP-hard even in restricted classes of trees such as bounded diameter spiders [Cicalese et al. 2016], and no constant factor approximation algorithm is known for general trees. Following the recent studies of [Dereniowski et al. 2022, Dereniowski et al. 2024], instead of restricted classes of trees, we explore restrictions on the cost function. We generalize the notion of up-monotonic functions and introduce the concept of k-up-modularity. We show that an O(loglog n)-approximate solution can be found within k^{O(log k)}\cdotpoly(n) time.

Citations

• Tight Approximation Bounds on a Simple Algorithm for Minimum Average Search Time in Trees
• Searching in trees with monotonic query times
• Fast approximation of search trees on trees with centroid trees
• On Dasgupta's hierarchical clustering objective and its relation to other graph parameters
• A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree
• Shortest path queries, graph partitioning and covering problems in worst and beyond worst case settings
• Approximation Strategies for Generalized Binary Search in Weighted Trees
• Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics
• A cost function for similarity-based hierarchical clustering
• Deterministic and Probabilistic Binary Search in Graphs
• Deterministic and probabilistic binary search in graphs
• On the Tree Search Problem with Non-uniform Costs
• Decision Trees for Function Evaluation - Simultaneous Optimization of Worst and Expected Cost
• On the Complexity of Searching in Trees: Average-case Minimization
• Cholesky Factorization of Matrices in Parallel and Ranking of Graphs

Cited by

• Approximating the Average-Case Graph Search Problem with Non-Uniform Costs

Related

• Searching in trees with monotonic query times
• On the Complexity of Searching in Trees: Average-case Minimization
• Search Trees on Trees via LP
• Approximation Strategies for Generalized Binary Search in Weighted Trees
• Approximating the Average-Case Graph Search Problem with Non-Uniform Costs