Approximating the Average-Case Graph Search Problem with Non-Uniform Costs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910053415518208 |
|---|---|
| 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 target vertex $x$ in a graph $G$. 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 in $G-v$ which contains $x$. Additionally, each vertex $v$ may have a different query cost $c(v)$ and a different weight $w(v)$. The goal is to find the optimal querying strategy which minimizes the weighted average-case cost required to find $x$. The problem is NP-hard even for uniform weights and query costs. Inspired by the progress on the edge query variant of the problem [SODA '17], we establish a connection between searching and vertex separation. By doing so, we provide an $O(\sqrt{\log n})$-approximation algorithm for general graphs and a $(4+ε)$-approximation algorithm for the case when the input is a tree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_06564 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating the Average-Case Graph Search Problem with Non-Uniform Costs Szyfelbein, Michał Data Structures and Algorithms G.2.2 Consider the following generalization of the classic binary search problem: A searcher is required to find a hidden target vertex $x$ in a graph $G$. 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 in $G-v$ which contains $x$. Additionally, each vertex $v$ may have a different query cost $c(v)$ and a different weight $w(v)$. The goal is to find the optimal querying strategy which minimizes the weighted average-case cost required to find $x$. The problem is NP-hard even for uniform weights and query costs. Inspired by the progress on the edge query variant of the problem [SODA '17], we establish a connection between searching and vertex separation. By doing so, we provide an $O(\sqrt{\log n})$-approximation algorithm for general graphs and a $(4+ε)$-approximation algorithm for the case when the input is a tree. |
| title | Approximating the Average-Case Graph Search Problem with Non-Uniform Costs |
| topic | Data Structures and Algorithms G.2.2 |
| url | https://arxiv.org/abs/2511.06564 |