Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.17887 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915522828828672 |
|---|---|
| author | Szyfelbein, Michał |
| author_facet | Szyfelbein, Michał |
| contents | 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 \textit{$k$-up-modularity}. We show that an $O(\log\log n)$-approximate solution can be found within $k^{O(\log k)}\cdot\text{poly}(n)$ time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17887 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Searching in trees with $k$-up-modular cost functions Szyfelbein, Michał Data Structures and Algorithms Discrete Mathematics G.2.2 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 \textit{$k$-up-modularity}. We show that an $O(\log\log n)$-approximate solution can be found within $k^{O(\log k)}\cdot\text{poly}(n)$ time. |
| title | Searching in trees with $k$-up-modular cost functions |
| topic | Data Structures and Algorithms Discrete Mathematics G.2.2 |
| url | https://arxiv.org/abs/2504.17887 |