Abstract
Prefetching constitutes a valuable tool toward the goal of 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 twoplayer 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 stepbystep traversing a subset of nodes in the Web graph, a satisfactory prefetching procedure would load in cache (without any delay) all resources lying in the neighborhood of this growing subset.
Motivated by the above, we consider the following maximization 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 NPhard 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 1/6(11/e)approximation algorithm for general graphs based on techniques for the Budgeted Connected Domination problem [Khuller et al., SODA 2014]. Finally, we provide a polynomialtime algorithm for the special case of interval graphs. Our algorithm returns an optimal solution for MRCE in O(n^3) time, where n is the number of nodes in G.
BibTeX  Entry
@InProceedings{lamprou_et_al:LIPIcs:2018:9607,
author = {Ioannis Lamprou and Russell Martin and Sven Schewe and Ioannis Sigalas and Vassilis Zissimopoulos},
title = {{Maximum Rooted Connected Expansion}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {25:125:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9607},
URN = {urn:nbn:de:0030drops96076},
doi = {10.4230/LIPIcs.MFCS.2018.25},
annote = {Keywords: prefetching, domination, expansion, ratio}
}
Keywords: 

prefetching, domination, expansion, ratio 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) 
Issue Date: 

2018 
Date of publication: 

20.08.2018 