## Sequences of Radius k for Complete Bipartite Graphs

### Michał Dębski , Zbigniew Lonc , Paweł Rzążewski

#### Abstract

Let $G$ be a graph. A emph{$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})leq(1+epsilon)d_kfrac{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)geq d_kfrac{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$.
 Author Pages 1-12 Publication size in sheets 0.55 Book Heggernes Pinar (eds.): GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2016, vol. 9941, 2016, SPRINGER INT PUBLISHING AG, ISBN 978-3-662-53536-3, [978-3-662-53535-6] Keywords in English sequence, k-radius sequences, bipartite graphs, maximum cut Abstract in Polish Ciągiem o promieniu k dla grafu G nazywamy ciąg wierzchołków grafu G (z możliwymi powtórzeniami), w którym końce każdej krawędzi występują jako elementy oddalone o co najwyżej k. W pracy pokazujemy, że problem znajdowania najkrótszego takiego ciągu jest problemem NP-trudnym. Ponadto pokazujemy dolne i górne ograniczenia na długość najkrótszego ciągu o promieniu k dla grafów pełnych dwudzielnych. DOI DOI:10.1007/978-3-662-53536-3_1 URL http://link.springer.com/chapter/10.1007/978-3-662-53536-3_1 Language en angielski Score (nominal) 15 Score Ministerial score = 15.0, 27-06-2017, BookChapterMatConfMinisterial score (2013-2016) = 15.0, 27-06-2017, BookChapterMatConf Citation count* 0
Cite