Michał Szyfelbein

Michał Szyfelbein

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.

Michał Szyfelbein

We 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$, by iteratively performing queries about vertices. A query to $v$ incurs a cost $c(v, x)$ and responds whether $v=x$ and if not, returns the connected component in $G-v$ containing $x$. The goal is to design a search strategy that minimizes the average-case search cost. Firstly, we consider the case when the cost of querying a vertex is independent of the target. We develop a $\br{4+ε}$-approximation FPTAS for trees running in $O(n^4/ε^2)$ time and an $O({\sqrt{\log n}})$-approximation for general graphs. Additionally, we give an FPTAS parametrized by the number of non-leaf vertices of the graph. On the hardness side we prove that the problem is NP-hard even when the input is a tree with bounded degree or bounded diameter. Secondly, we consider trees and assume $c(v, x)$ to be a monotone non-decreasing function with respect to $x$, i.e.\ if $u \in P_{v, x}$ then $c(u, x) \leq c(v, x)$. We give a $2$-approximation algorithm which can also be easily altered to work for the worst-case variant. This is the first constant factor approximation algorithm for both criterions. Previously known results only regard the worst-case search cost and include a parametrized PTAS as well as a $4$-approximation for paths. At last, we show that when the cost function is an arbitrary function of the queried vertex and the target, then the problem does not admit any constant factor approximation under the UGC, even when the input tree is a star.