Search papers, labs, and topics across Lattice.
This paper investigates the average-case graph searching problem, where the cost of querying a vertex depends on the target and the response indicates the connected component containing the target. For the case where query costs are independent of the target, the authors develop a $(4+\epsilon)$-approximation FPTAS for trees and an $O(\sqrt{\log n})$-approximation for general graphs. They also present a 2-approximation algorithm for trees with monotone non-decreasing cost functions, improving upon previous worst-case search cost results.
Finding a hidden node in a graph just got a whole lot faster: a new algorithm slashes the average search cost with provable approximation guarantees, even with non-uniform query costs.
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+\epsilon}$-approximation FPTAS for trees running in $O(n^4/\epsilon^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.
