  We study the problem of searching for a hidden target in an environment that
is modeled by an edge-weighted graph. A sequence of edges is chosen starting
from a given root vertex such that each edge is adjacent to a previously chosen
edge. This search paradigm, known as expanding search was recently introduced
by Apern and Lidbetter [2013] for modeling problems such as searching for coal
or minesweeping in which the cost of re-exploration is negligible. It can also
be used to model a team of searchers successively splitting up in the search
for a hidden adversary or explosive device, for example. We define the search
ratio of an expanding search as the maximum over all vertices of the ratio of
the time taken to reach the vertex and the shortest-path cost to it from the
root. This can be interpreted as a measure of the multiplicative regret
incurred in searching, and similar objectives have previously been studied in
the context of conventional (pathwise) search. In this paper we address
algorithmic and computational issues of minimizing the search ratio over all
expanding searches, for a variety of search environments, including general
graphs, trees and star-like graphs. Our main results focus on the problem of
finding the randomized expanding search with minimum expected search ratio,
which is equivalent to solving a zero-sum game between a Searcher and a Hider.
We solve these problems for certain classes of graphs, and obtain
constant-factor approximations for others.
