  To tackle the expected enormous increase in mobile video traffic in cellular
networks, an architecture involving a base station along with caching femto
stations (referred to as helpers), storing popular files near users, has been
proposed [1]. The primary benefit of caching is the enormous increase in
downloading rate when a popular file is available at helpers near a user
requesting that file. In this work, we explore a secondary benefit of caching
in this architecture through the lens of index coding. We assume a system with
n users and constant number of caching helpers. Only helpers store files, i.e.
have side information. We investigate the following scenario: Each user
requests a distinct file that is not found in the set of helpers nearby. Users
are served coded packets (through an index code) by an omniscient base station.
Every user decodes its desired packet from the coded packets and the side
information packets from helpers nearby. We assume that users can obtain any
file stored in their neighboring helpers without incurring transmission costs.
With respect to the index code employed, we investigate two achievable schemes:
1) XOR coloring based on coloring of the side information graph associated with
the problem and 2)Vector XOR coloring based on fractional coloring of the side
information graph. We show that the general problem reduces to a canonical
problem where every user is connected to exactly one helper under some
topological constraints. For the canonical problem, with constant number of
helpers (k), we show that the complexity of computing the best XOR/vector XOR
coloring schemes are polynomial in the number of users n. The result exploits a
special complete bi-partite structure that the side information graphs exhibit
for any finite k.
