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

arXiv: https://arxiv.org/abs/2511.06564 · HTML: https://mlsanity.com/paper/2511.06564/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2025.

## Built on by (most cited first, 1 of 1)

- [Precedence-Constrained Decision Trees and Coverings](https://mlsanity.com/paper/2602.21312/) (2026)

## Abstract (arXiv)

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(√log n)-approximation algorithm for general graphs and a (4+ε)-approximation algorithm for the case when the input is a tree.