  Prefetching constitutes a valuable tool toward efficient Web surfing. As a
result, estimating the amount of resources that need to be preloaded during a
surfer's browsing becomes an important task. In this regard, prefetching can be
modeled as a two-player combinatorial game [Fomin et al., Theoretical Computer
Science 2014], where a surfer and a marker alternately play on a given graph
(representing the Web graph). During its turn, the marker chooses a set of $k$
nodes to mark (prefetch), whereas the surfer, represented as a token resting on
graph nodes, moves to a neighboring node (Web resource). The surfer's objective
is to reach an unmarked node before all nodes become marked and the marker
wins. Intuitively, since the surfer is step-by-step traversing a subset of
nodes in the Web graph, a satisfactory prefetching procedure would load in
cache all resources lying in the neighborhood of this growing subset.
  Motivated by the above, we consider the following problem to which we refer
to as the Maximum Rooted Connected Expansion (MRCE) problem. Given a graph $G$
and a root node $v_0$, we wish to find a subset of vertices $S$ such that $S$
is connected, $S$ contains $v_0$ and the ratio $|N[S]|/|S|$ is maximized, where
$N[S]$ denotes the closed neighborhood of $S$, that is, $N[S]$ contains all
nodes in $S$ and all nodes with at least one neighbor in $S$.
  We prove that the problem is NP-hard even when the input graph $G$ is
restricted to be a split graph. On the positive side, we demonstrate a
polynomial time approximation scheme for split graphs. Furthermore, we present
a $\frac{1}{6}(1-\frac{1}{e})$-approximation algorithm for general graphs based
on techniques for the Budgeted Connected Domination problem [Khuller et al.,
SODA 2014]. Finally, we provide a polynomial-time algorithm for the special
case of interval graphs.
