Sequences of Radius k for Complete Bipartite Graphs

Abstract

Let G be a graph. A k-radius sequence for G is a sequence of vertices of G such that for every edge uv of G vertices u and v appear at least once within distance k in the sequence. The length of a shortest k-radius sequence for G is denoted by $f_k(G)$.

Such sequences appear in a problem related to computing values of some 2-argument functions. Suppose we have a set V of large objects, stored in an external database, and our cache can accommodate at most $k+1$ objects from V at one time. If we are given a set E of pairs of objects for which we want to compute the value of some 2-argument function, and assume that our cache is managed in FIFO manner, then $f_k(G)$ (where $G=(V,E)$) is the minimum number of times we need to copy an object from the database to the cache.

We give an asymptotically tight estimation on $f_k(G)$ for complete bipartite graphs. We show that for every $\epsilon >0$ we have $f_k(K_{m,n})\le (1+\epsilon )d_k\frac{mn}{k}$, provided that both m and n are sufficiently large – where $d_k$ depends only on k. This upper bound asymptotically coincides with the lower bound $f_k(G)\ge d_k\frac{e(G)}{k}$, valid for all bipartite graphs.

We also show that determining $f_k(G)$ for an arbitrary graph G is NP-hard for every constant $k>1$.

Research supported by the Polish National Science Center, decision nr DEC-2012/05/B/ST1/00652.