{"ID":2844484,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.06564","arxiv_id":"2511.06564","title":"Approximating the Average-Case Graph Search Problem with Non-Uniform Costs","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2511.06564","url_pdf":"https://arxiv.org/pdf/2511.06564v1","authors":"[\"Michał Szyfelbein\"]","published":"2025-11-09T22:53:07Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}