Storage Capacity as an Information-Theoretic
Analogue of Vertex Cover*

arXiv:1706.09197v1 [cs.IT] 28 Jun 2017

Arya Mazumdar

Andrew McGregor

Sofya Vorotnikova

Abstract
Motivated by applications in distributed storage, the storage capacity of a graph was recently defined
to be the maximum amount of information that can be stored across the vertices of a graph such that
the information at any vertex can be recovered from the information stored at the neighboring vertices.
Computing the storage capacity is a fundamental problem in network coding and is related, or equivalent,
to some well-studied problems such as index coding with side information and generalized guessing
games. In this paper, we consider storage capacity as a natural information-theoretic analogue of the
minimum vertex cover of a graph. Indeed, while it was known that storage capacity is upper bounded by
minimum vertex cover, we show that by treating it as such we can get a 3/2 approximation for planar
graphs, and a 4/3 approximation for triangle-free planar graphs. Since the storage capacity is intimately
related to the index coding rate, we get a 2 approximation of index coding rate for planar graphs1 and
3/2 approximation for triangle-free planar graphs. Previously only a trivial 4 approximation of the index
coding rate was known for planar graphs. We then develop a general method of “gadget covering” to
upper bound the storage capacity in terms of the average of a set of vertex covers. This method is intuitive
and leads to the exact characterization of storage capacity for various families of graphs. As an illustrative
example, we use this approach to derive the exact storage capacity of cycles-with-chords, a family of
graphs related to outerplanar graphs. Finally, we generalize the storage capacity notion to include recovery
from partial failures in distributed storage. We show tight upper and lower bounds on this partial recovery
capacity that scales nicely with the fraction of failure in a vertex.

1

Introduction

The Shannon capacity of a graph [18] is a well studied parameter that quantifies the zero-error capacity of a
noisy communication channel. There are also several other notions of graph capacities or graph entropies that
model different communication/compression scenarios (for example, see [1]). In this paper, we are interested
in a very recent definition of graph capacity, called the storage capacity, that we consider to be a natural
information-theoretic analogue of the minimum vertex cover of a graph.
* University of Massachusetts, Amherst. {arya,mcgregor,svorotni}@cs.umass.edu. This work was supported by
NSF Awards CCF-0953754, IIS-1251110, CCF-1320719, CCF-1642658, CCF-BSF-1618512, and a Google Research Award.
1
A shorter version of this paper in the proceedings of the IEEE International Symposium on Information Theory, 2017 contains an
error. The approximation factor for index coding rate for planar graphs was wrongly claimed to be 1.923. The correct approximation
factor of our method is 2, and we have corrected Theorem 3 in this version.

1

Suppose, every vertex of a graph can store a symbol (from any alphabet) with the criterion that the
content of any vertex can be uniquely recovered from the contents of its neighborhood in the graph. Then
the maximum amount of information that can be stored in the graph is called the storage capacity of that
graph [17]. This formulation is mainly motivated by applications in distributed storage, and generalizes
the popular definition of locally repairable codes [13]. In a distributed storage system, each symbol (or
coordinate) of a codeword vector is stored at a different server or storage vertex. In the case of a single server
failure, it is desirable to be able to recover the data of that server by accessing a small number of other servers.
Given the topology of the storage network as a graph, it is quite natural to model the local repair problem as a
neighborhood repair problem as above.
Formally, suppose we are given an n-vertex graph G(V, E), where V = [n] ≡ {1, 2, . . . , n}. Also, given
a positive integer q ≥ 2, let H(X) be the Shannon entropy of the random variable X in q-ary units (for
example, when q = 2, the entropy is in bits). Let {Xi }i∈V , be random variables each with a finite sample
space of size q. For any I ⊆ [n], let XI ≡ {Xi : i ∈ I}. Consider the solution of the following optimization
problem:
max H(X1 , . . . , Xn )

(1)

such that
H(Xi |XN (i) ) = 0,
for all i ∈ V where N (i) = {j ∈ V : (i, j) ∈ E} is the set of neighbors of vertex i. This is the storage
capacity of the graph G and we denote it by Capq (G). Note that, although we hide the unit of entropy in
the notation H(·), the unit should be clear from context, and the storage capacity should depend on it, as
reflected in the subscript in the notation Capq (G). The absolute storage capacity is defined to be,
Cap(G) = lim Capq (G).
q→∞

(2)

In [17], it was observed that the storage capacity is upper bounded by the size of the minimum vertex
cover VC(G) of the graph G.
Cap(G) ≤ | VC(G)|.

(3)

The proof of this fact is quite simple. Since all the neighbors of V \ VC belong to VC,
H(XV ) = H(XVC , XV \VC(G) ) = H(XVC(G) ) + H(XV \VC(G) |H(XVC(G) )) = H(XVC(G) ) ≤ | VC(G)|.
Indeed, this proof shows that H(XV ) = H(XVC(G) ). Because of this, we think it is natural to view storage
capacity as an information theoretic analogue of vertex cover. It was also shown in [17] that the storage
capacity is at least equal to the size MM(G) of the maximum matching of the graph G:
MM(G) ≤ Cap2 (G) ≤ Cap(G).

(4)

Since maximum matching and minimum vertex cover are two quantities within a factor of two of each other
and maximum matching can be found in polynomial time, this fact gives a 2-approximation of the storage
capacity2 . Improvement of this approximation factor is unlikely to be achieved by simple means, since that
would imply a better-than-2 approximation ratio for the minimum vertex cover problem violating the unique
games conjecture [15].
2

Indeed, finding a maximal matching is sufficient for this purpose.

2

This motivates us to look for natural families of graphs where minimum vertex cover has a better
approximation. For example, for bipartite graphs maximum matching is equal to minimum vertex cover and
hence storage capacity is exactly equal to the minimum vertex cover. Other obvious class, and our focus in
Section 3, is the family of planar graphs for which a PTAS is known [4, 5]. Another motivation for studying
storage capacity on planar graphs is that they represent common network topologies for distributed systems.
For example, see [10] to note how a surprising number of data networks are actually planar. To minimize
interference, it is natural for a distributed storage system to be arranged as a planar network. Moreover it is
useful to have wireless networks, video-on-demand networks etc. that are planar or almost planar.
Video-on-demand also motivates a related broadcast problem called index coding [6] for which planar
topologies are of interest, and outerplanar topologies have already been studied [7]. It was shown in [17] that
storage capacity is, in a coding-theoretic sense, dual to index coding and is equivalent to the guessing game
problem of [12]. The index coding rate for a graph G is defined to be the optimum value of the following
minimization problem:
min H(Y )

(5)

where Y is such that
H(Xi |Y, XN (i) ) = 0,
for all i ∈ V . This is called the optimum index coding rate for the graph G, and we denote it as Indq (G). We
can also define,
Ind(G) = lim Indq (G).
q→∞

(6)

The index coding problem is the hardest of all network coding problems and has been the subject of much
recent attention, see, e.g., [16]. In particular it can be shown that any network coding problem can be reduced
to an index coding problem [11]. It has been shown [17] that,
Cap(G) = n − Ind(G).

(7)

and hence exact computation of Ind(G) and Cap(G) is equivalent although the approximation hardness
could obviously differ. Note that,
Ind(G) ≥ α(G),
where α(G) is the independence number of G. Since, for planar graphs α(G) ≥ n/4, taking Y to be X[n]
already gives a 4-approximation for index coding rate for planar graphs (since H(Y ) ≤ n). In this paper,
we give a significantly better approximation algorithm for index coding rate of planar graphs. Not only that,
due to the relation between index coding rate and storage capacity, we can obtain an approximation factor
significantly better than 2 for storage capacity. Note that, even to approximate the optimal index coding rate
within a factor of n1− seems to be a challenge [9].
To go beyond the realm of planar graphs, and to obtain better approximation ratios, we then develop
several upper bounding tools for storage capacities. In particular by using these tools, we are able to exactly
characterize storage capacities of various families of graphs. Our approach revisits a linear program proposed
by Blasiak, Kleinberg, and Lubetzky [8] that can be used to lower bound the optimum index coding rate
or upper bound the storage capacity. We transform the problem of bounding this LP into the problem of
constructing a family of vertex covers for the input graph. This in turn allows us to upper bound the storage
capacity of any graph that admits a specific type of vertex partition. We then identify various graphs for
which this upper bound is tight.
3

Since, the storage capacity, or the vertex cover, act as absolute upper bounds on the rate of information
storage in the graph, a natural question to ask is, if we store above the limit of minimum vertex cover in the
graph, will any of the repair property be left? This is similar in philosophy to the rate-distortion theory of data
compression, where one compresses beyond entropy limit and still can recover the data with some distortion.
This question gives rise to the notion of recovery from partial failure, as defined below.
We define the partial repair capacity also keeping the application of distributed storage in mind. This is
a direct generalization in the context of distributed storage application to handle partial failure of vertices.
In particular, suppose we lose 0 ≤ δ ≤ 1 proportion of the bits stored in a vertex. We still want to recover
these bits by accessing the remaining (1 − δ)-fraction of the bits in the vertex plus the contents of the
neighborhood. What is the maximum amount of information that can be stored in the network with such
restriction? Intuitively, the storage capacity should increase. We characterize the trade-off between δ and
this increase in storage capacity from both sides (i.e., upper and lower bounds on the capacity). A surprising
fact that we observe is that, if we want to recover from more than half of the bits being lost, then there is no
increase in storage capacity.
In summary, we made progress on the study of storage capacity on three fronts:
• Planar graphs. We prove a 3/2 approximation of storage capacity and 2 approximation for index
coding rate for planar graphs. We provide an approximation guarantee that depends on the number of
triangle in the graph and, in the special case of for triangle-free graphs, we get a 4/3 approximation for
storage capacity, and 3/2 approximation for index coding rate.
• Tools for finding storage capacity upper bounds. We develop an approach for bounding storage capacity
in terms of a small number of vertex covers. We first illustrate this approach by finding the exact
storage capacity of some simple graphs. We then use the approach to show a bound on any graph that
admits a specific type of vertex partition. With this we prove exact bounds on a family of Cartesian
product graphs and a family closely related to outerplanar graphs.
• Partial failure recovery. We show that if recovery from neighbors is possible for up to δ-proportion
failure of the bits stored in a server, then the capacity is upper bounded by the optimum value of a linear
program; in particular this implies when δ ≥ 12 , then the partial recovery capacity is same as the storage
capacity. For an odd cycle, the upper bound on partial recovery capacity is given by n2 (1 + R2 (δ)),
where R2 (δ) is the maximum achievable rate of a binary error-correcting code with relative minimum
Hamming distance at least δn. On the other hand, we also obtain general lower bounds on the partial
recovery capacity of a graph. For an odd cycle, our results imply that a partial failure recovery capacity
of n2 (2 − h2 (δ)) is polynomial time achievable, where h2 (δ) denotes the binary entropy function. Our
bounds are very tight, since it is a widely believed conjecture that R2 (δ) = 1 − h2 (δ).

2

Preliminaries

Let CP(G) denote the fractional clique packing of a graph defined as follows: Let C be the set of all
cliques
in G. For every C ∈ C define a variable 0 ≤ xC ≤ 1. Then CP(G) is the maximum values of
P
C∈C xC (|C| − 1) subject to the constraint that
X
xC ≤ 1
∀u ∈ V
C∈C:u∈C

Note that CP(G) can be computed in polynomial time in graphs, such as planar graphs, where all cliques
have constant size. Furthermore, CP(G) is at least the size of the maximum fractional matching and they are
obviously equal in triangle-free graphs since the only cliques are edges.
4

The following preliminary lemma shows that Capq (G) ≥ CP(G) for sufficiently large q. An equivalent
result is known in the context of index coding but we include a proof here for completeness. The basic idea is
that we can store k − 1 information on a clique of size k by assigning k − 1 independent uniform random
variables to k − 1 of the vertices and setting the final random variable to the sum (modulo q) of the first k − 1
random variables.
Lemma 1. Capq (G) ≥ CP(G) for sufficiently large q.
Proof. Let {xC }C∈C achieve CP(G). Let q be sufficiently large such that q xC is integral for every C. For
each clique C = {u1 , . . . , u|C| } in the graph, define a family of random variables XuC1 , XuC2 , . . . , XuC|C|
where XuC1 , XuC2 , . . . , XuC|C|−1 are independent and uniform over {0, 1, . . . , q xC − 1} and
|C|−1

XuC|C|

=

X

XuCi mod q xC .

i=1

Note that each XuCi can be deduced from {XuCj }j6=i and the entropy of {XuCj }j6=i is xC (|C| − 1). Finally,
C
let Xu be an encoding
P of {Xu }C∈C:u∈C as a symbol from a q-ary alphabet; the fact that this is possible
followings because C∈C:u∈C xC ≤ 1. Then the entropy of XV is CP(G) as required.
Notation. Let G[S] denote the subgraph induced by S ⊆ V . Let α(G) be the size of the largest independent
set and let VC(G) be the size of minimum vertex cover. Let MM(G) be the size of the largest matching and
let FM(G) be the weight of the maximum fractional matching.

3

Approximation Algorithms for Planar Graphs via Vertex Cover

In this section, we present approximation results for the storage capacity and optimal index coding rate of
planar graphs. Specifically we show that CP(G) can be used to achieve a 3/2 approximation of the storage
capacity and a 2 approximation of the optimal index coding rate.
In our storage capacity result we use ideas introduced by Bar-Yehuda and Even [5] for the purpose of
5/3-approximating the vertex cover in planar graphs. Specifically, they first considered a maximal set of
vertex-disjoint triangles, reasoned about the vertex cover amongst these triangles, and then reasoned about the
triangle-free induced subgraph on the remaining vertices. We consider a similar decomposition and reason
about the integrality gap of vertex cover in each component. We parameterize our result in terms of the
number of triangles; this will be essential in the subsequent result on optimal index coding rate.
Theorem 2. Assume G is planar and let T be a set of 3t vertices corresponding to maximal set of t vertex
disjoint triangles. Then,
Cap(G)
3t + k
1≤
≤
CP(G)
2t + 3k/4
where k is the size of the minimum vertex cover of G[V \ T ]. Hence CP(G) is a 3/2 approximation for
Cap(G) and 4/3 approximation if G is triangle-free.
Proof. Let G0 = G[V \ T ]. Partition the set of vertices into T ∪ C ∪ I where C is the minimum vertex cover
of G0 and I ⊂ V \ T is therefore an independent set. Let XV be the set of variables that achieve storage
capacity. Therefore,
Cap(G) = H(XV ) = H(XT ) + H(XC |XT ) + H(XI |XC , XT ) ≤ H(XT ) + H(XC |XT ) ≤ 3t + k
5

since for each v ∈ I, H(Xv |XC , XT ) = 0 since N (v) ⊂ C ∪ T .
Consider the fractional clique packing in which each of the t vertex-disjoint triangles in T receive
weight 1. Then, CP(G) ≥ 2t + CP(G0 ). Then it remains to show that CP(G0 ) ≥ 3k/4. Note that since
G0 is triangle-free planar graph, it is 3-colorable by Grötzsch’s theorem [14]. Furthermore, CP(G0 ) is the
maximum fractional matching which, by duality, is the minimum fractional vertex cover. Hence it suffices
to show that the size of the minimum fractional vertex cover of 3-colorable graph is at least 3/4 of the size
of the minimum (integral) vertex cover, i.e., 3k/4. This can be shown as follows. Let x1 , . . . , xn be an
optimal fractional vertex cover, i.e., for all edges uv ∈ G0 , xu + xv ≥ 1. Since fractional vertex cover is
1/2-integral, we may assume each xu ∈ {0, 1/2, 1}. Let I1 , I2 , I3 be a partitioning of {u ∈ [n] : xu = 1/2}
corresponding to a 3-coloring where
X
X
X
xv ≥
xv ≥
xv .
v∈I1

v∈I2

v∈I3

Then consider y1 , . . . , yn where yu = 1 iff u ∈ I2 ∪ I3 or xu = 1. Then
X
X
X
X
X
yu ≤
yu +
yu ≤ 2/3 · 2 ·
xu +
xu ≤ 4/3 · CP(G0 ) ,
u∈[n]

u∈I2 ∪I3

u∈[n]:xu =1

u:xu =1/2

u:xu =1

and y1 , . . . , yn is a vertex cover because for every edge uv, at least one endpoint one of {xu , xv } is 1 or at
least one of u and v is in I2 ∪ I3 .
We next use the result of the previous theorem, together with the chromatic number of planar and
triangle-free planar graphs to achieve a 2 approximation for Ind(G).
Theorem 3. Assume G is planar and let T be a set of 3t vertices corresponding to t vertex disjoint triangles.
Then,

n
 3n+3t + 34 for t ≤ 12
n − CP(G)  4n−12t
n
1≤
≤ nt + 74
for 12
≤ t ≤ n4 .

Ind(G)

for t ≥ n4
4 − 8t
n
Maximizing over t implies that n − CP(G) is a 2 approximation for Ind(G) and a 3/2 approximation if G is
triangle-free.
Proof. From Theorem 2, we know that CP(G) ≥ 2t + 3/4 VC(G0 ) where G0 = G[V \ T ]. Therefore, we
can bound n − CP(G) as follows:
n − CP(G) ≤ n − (2t + 3/4 VC(G0 ))
= n − (2t + 3/4(n − 3t − α(G0 )))
= (n + t)/4 + 3/4 α(G0 )
On the other hand,
Ind(G) ≥ α(G) ≥ α(G0 )
where α denotes the size of the maximum independent set of the graph. Note that α(G) ≥ n/4 since G
is planar and thus 4-colorable [2, 3]. Since G0 has n − 3t vertices and is triangle-free and planar and thus

6

3-colorable [14], n − 3t ≥ α(G0 ) ≥ (n − 3t)/3. By combining inequalities above we get


n − CP(G)
(n + t)/4 + 3/4 α(G0 ) (n + t)/4 + 3/4 α(G0 ) (n + t)/4 + 3/4 α(G)
≤ min
,
,
Ind(G)
α(G)
α(G0 )
α(G)


(n + t)/4 + 3/4(n − 3t) (n + t)/4
(n + t)/4
≤ min
,
+ 3/4,
+ 3/4
n/4
(n − 3t)/3
n/4


7
8t 3n + 3t 3 t
.
+ , +
= min 4 − ,
n 4n − 3t 4 n 4

4

Upper Bounds on Storage Capacity via Multiple Vertex Covers

In this section, we start by considering a linear program proposed by Blasiak, Kleinberg, and Lubetzky [8]
that can be used to lower bound the optimum index coding rate or upper bound the storage capacity.3
Unfortunately there are Ω(2n ) constraints but by carefully selecting a subset of constraints we can prove
upper bounds on the storage capacity for a specific graph without solving the LP.
Our main goal in this section is to relate this linear program to a finding a suitable family of vertex covers
of the graph. In doing so, we propose a most combinatorial “gadget” based approach to constructing good
upper bounds that we think makes the process of proving strong upper bounds more intuitive. This allows
us to prove a more general theorem that gives an upper bound on the storage capacity for a relatively large
family of graphs. As an application of this theorem we show that a class of graphs closely related to the
family of outerplanar graphs and another family of cartesian product graphs have capacity exactly n/2.

4.1

Upper Bound via the “Information Theoretic” LP

We first rewrite the index coding LP proposed by Blasiak, Kleinberg, and Lubetzky [8] for the purposes of
upper-bounding storage capacity. We define a variable zS for every S ⊆ V that will correspond to an upper
bound for H(XS ). Let cl(S) = S ∪ {v : N (v) ⊆ S} denote the closure of the set S consisting of vertices in
S and vertices with all neighbors in S.
maximize zV
s.t. z∅ = 0
zT − zS ≤ |T \ cl(S)|
zS + zT ≥ zS∩T + zS∪T

∀S ⊆ T
∀S, T

The second constraint corresponds to
H(XT ) − H(XS ) = H(XT |XS ) = H(XT |Xcl(S) ) ≤ H(XT \cl(S) ) ≤ |T \ cl(S)| ,
whereas the last constraint follows from the sub-modularity of entropy. Hence, the optimal solution to the
above LP is an upper bound on Cap(G). We henceforth refer to the above linear program as the information
theoretic LP.
3

Blasiak et al. only consider index coding but it is straightforward to adapt the LP in a natural way for storage capacity; see below.

7

4.2

Upper Bound via Gadgets

k-cover by gadgets is a technique for proving upper bounds on the storage capacity of graph. The core idea
is to construct a set of k vertex covers for the graph via the construction of various gadgets which we now
define.
A gadget g(A, B) is created the following way: take two sets of vertices A and B, take their closures
cl(A) and cl(B), find S = cl(A) ∪ cl(B) and T = cl(A) ∩ cl(B). Then S and T form a gadget. Call S
the outside of the gadget and T the inside. We note that by taking A = {v} and B = ∅ we obtain a gadget
with the outside {v} and empty inside (assuming v has no neighbors of degree one); call such gadget trivial.
Define the weight of a gadget to be |A| + |B|. If we color every inside and outside gadget set with one of k
colors such that the union of all sets of the same color forms a vertex cover, the total weight of gadgets in such
coloring provides an upper bound on k Cap(G). Note that for k = 1 using gadgets with non-empty inside
can only increase the total weight, so the only gadgets we need to consider are the trivial ones corresponding
to individual vertices, and thus the construction is just a single vertex cover.
We can formulate the k-cover by gadgets (for fixed k) as the following linear program: Let xS,c be a
variable where S is a set that is an outside or an inside of a gadget and c is one of k colors. Each variable has
a corresponding weight wS,c = (|A| + |B|)/2 where A and B are the 2 sets used to form the gadget that S is
a part of. xS,c = 1 if set S is colored with color c and 0 otherwise.
minimize
s.t.

1X
wS,c xS,c
k
S,c
X
X
xS,c +
xS,c ≥ 1
S:u∈S

X
c

∀(u, v) ∈ E, ∀c

S:v∈S

xH,c =

X

xH 0 ,c

c

for all gadgets, where H is the outside of the gadget and
H 0 the inside of the same gadget

The first condition states that every collection of sets of a certain color is a vertex cover and the second one
states that the outside and inside of every gadget are used the same number of times.
Theorem 4. Any feasible integral solution to the above k-cover by gadgets LP is an upper bound on Cap(G).
Proof. We prove this by showing that k-cover by gadgets follows from the fact that the optimum solution
of the information theoretic LP is an upper bound. First, note which constraints correspond to the steps of
forming a gadget:
zA ≤ |A| take set A
zB ≤ |B| take set B
zcl(A) − zA ≤ 0 find closure of A
zcl(B) − zB ≤ 0 find closure of B
zS + zT ≤ zcl(A) + zcl(B)

find S = cl(A) ∪ cl(B) and T = cl(A) ∩ cl(B)

If we sum all the constraints, we obtain zS + zT ≤ |A| + |B|. Assume, that we used g gadgets in the cover.
Then by summing all corresponding constraints, we get
zS1 + zT1 + zS2 + zT2 + · · · + zSg + zTg ≤ |A1 | + |B1 | + · · · + |Ag | + |Bg |

8

4

5

3

6

1
9

2

8

3
7

9
2

7

1

8

4
6

5

(a) An Odd Cycle.

(b) An Outerplanar Graph.

Figure 1: Two examples of k-cover upper bounds. See text for details.

Group the sets into color classes C1 , C2 , . . . , Ck . Let Ui =

S

S. The corresponding constraints are then

S∈Ci

zUi −

X

zS ≤ 0 ∀i ∈ {1, 2, . . . , k}

S∈Ci

zcl(Ui ) − zUi ≤ 0 ∀i ∈ {1, 2, . . . , k}
Note that zV = zcl(Ui ) since Ui is a vertex cover. By summing these 2k constraints and the one obtained
from building gadgets, we get kzV ≤ |A1 | + |B1 | + · · · + |Ag | + |Bg |.
4.2.1

Examples

We next illustrate the use of the k-cover via gadgets approach with a couple of examples. First, we re-prove a
result of Blasiak et al. [9] via a 2-cover by gadgets. Then we give an example of an outerplanar graph where
it is necessary to consider a 3-cover by gadgets in order to establish a tight bound.
Odd Cycles. We prove that the storage capacity of an odd cycle of length n is n/2; see Figure 1(a) for
an example where n = 9. FM(Cn ) = n/2, thus Cap(Cn ) ≥ n/2. For the upper bound we form a gadget
g(A, B) by taking A = {v1 , v3 }, B = {v2 , v4 } and obtaining outer set S = {v1 , v2 , v3 , v4 } and inner
set T = {v2 , v3 }. On the rest of the vertices we place trivial gadgets. Color S and trivial gadgets on
v6 , v8 , . . . , vn−1 green, color T and trivial gadgets on v5 , v7 , . . . , vn red. Green and red sets are then vertex
covers and the total weight of all gadgets is n. Thus, Cap(Cn ) ≤ n/2.
An Outerplanar Graph. We prove that the storage capacity of the graph in Figure 1(b) is 14/3. This
capacity is achieved by the fractional clique cover. Create a gadget g1 (A1 , B1 ) from A1 = {v1 , v3 } and
B1 = {v2 , v4 } and another gadget g2 (A2 , B2 ) from A2 = {v5 , v7 } and B2 = {v6 , v8 }. Place 1 trivial gadget
on each of the vertices v2 , v4 , v5 , v7 and 2 trivial gadgets on v9 . Color the sets as follows:
• Red: v5 , v7 , v9 and the inside of gadget g1
• Blue: v2 , v4 , v9 and the inside of gadget g2
• Green: the outside sets of both gadgets
Note that vertices of every color class form a vertex cover and the total weight of gadgets is 14.
9

(a) Graph G. Shaded vertices are X = SX .

(b) Graph G[Y ]. Shaded vertices are SY .

Figure 2: Example of storage capacity proof for a cartesian product graph G formed from a 5-cycle and a
length 3 path. See text for details.

4.3 n/2 Upper Bound via Vertex Partition
The next theorem uses a 2-cover by gadgets to prove that a certain family of graphs have capacity at most
n/2. Subsequently, we will use this theorem to exactly characterize the capacity of various graph families of
interest.
Theorem 5. Suppose that the vertices of a graph G can be partitioned into sets X and Y such that:
1. G[X] and G[Y ] are both bipartite.
2. SX is an independent set in G[X] and SY is an independent set in G[Y ]
where SX ⊆ X consists of all vertices in X with a neighbor in Y and SY ⊆ Y consists of all vertices in Y
with a neighbor in X. Then Cap(G) ≤ n/2.
Proof. We prove this theorem by showing that G has a 2-cover by gadgets of total weight n. First, form
a gadget gX (A, B) by letting (A, B) be a bipartition of the vertices of G[X]. Note that the vertices in X
that are in the outside set of the gadget but not in the inside set, are exactly the vertices in SX . This follows
because for v ∈ X, v ∈ cl(A) ∩ cl(B) iff all of v’s neighbors are in X. Similarly, form gY . Color the inside
of gX and the outside of gY red. Color the outside of gX and the inside of gY blue. Observe that both color
classes are vertex covers and the total weight of the 2 gadgets is |X| + |Y | = n.
4.3.1

Cartesian Product of a Cycle and a Bipartite Graph

The Cartesian product of graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) is denoted by G1 G2 and defined as
follows:
• The vertex set is the Cartesian set product V1 × V2
• (u, u0 )(v, v 0 ) is an edge iff u = v and u0 v 0 ∈ E2 or u0 = v 0 and uv ∈ E1
We next use Theorem 5 to show that any Cartesian Product of a cycle and a bipartite graph has storage
capacity exactly n/2.
Theorem 6. Let Ck be a cycle with k > 3, B a bipartite graph, and G = Ck B. Then Cap(G) = n/2,
where n is the number of vertices in G.

10

Proof. If k is even, G is a bipartite graph with MM(G) = VC(G) = n/2 and hence Cap(G) = n/2.
Assume for the rest of the proof that k is odd.
To show that Cap(G) ≥ n/2, consider the fractional matching where we assign weight 1/2 to all edges
of the form (u, a)(v, a), i.e., edges that come from the cycle. Hence Cap(G) ≥ n/2.
To show that Cap(G) ≤ n/2 we proceed as follows. Consider the subgraph induced by vertices (ui , v1 ),
(ui , v2 ), (ui , v3 ), etc., which is isomorphic to B. Color it using 2 colors and call the vertices of each color Ri
and Qi respectively. We now show that X = R1 ∪ Q2 and Y = V \ X satisfy the conditions of theorem
5. G[X] has no edges and therefore is bipartite. G[Y ] is bipartite because it consists of Pk−3 B which
is bipartite (where Pk−3 is a path of length k − 3 obtained by deleting edges uk u1 , u1 u2 , and u2 u3 from
the cycle), edges between Rk and R1 , and edges between Q2 and Q3 which do not complete any cycles.
SX = X is an independent set. SY = Rk ∪ Q1 ∪ R2 ∪ Q3 is also an independent set.
4.3.2

Cycles With Chords That Are Not Too Close Together

We next apply Theorem 5 to prove that a family of graphs related to outerplanar graphs also has storage
capacity n/2. Recall that any (connected) outerplanar graph without cut vertices is a cycle with nonoverlapping chords. The family of graphs we consider is more general in the sense that we permit the chords
to overlap but more restrictive in the sense that we require the endpoints of these chords to be at least a
distance 4 apart on the cycle. A natural open question is to characterize Cap(G) for all outerplanar graphs.
All that was previously known is that if we assume each Xi is a linear combination of {Xj }j∈N (i) , then
Cap(G) equals integral clique packing [7].
Theorem 7. Let G be a cycle with a number of chords such that endpoints of chords are at least distance 4
apart on the cycle. Then Cap(G) = n/2.
Proof. To show that Cap(G) ≥ n/2, consider the fractional matching where we place weight 1/2 on every
edge of the cycle. To show that Cap(G) ≤ n/2 we proceed as follows. Label the vertices that are endpoints
of chords c1 , c2 , . . . , ck in the order they appear on the cycle. For every path between ci and ci+1 (and
between ck and c1 ) pick the middle vertex of the path to be included in X. If the path is of odd length, pick
any of the 2 middle vertices. We now show that X and Y = V \ X satisfy the conditions of theorem 5.
X = SX is an independent set. G[Y ] is a forest and SY is an independent set due to the assumption on the
distance between chord endpoints.

5

Partial Recovery

In this section, we extend the notion of storage capacity to cover for partial failures. This is a new generalization, that, as far as we understand, does not have a counterpart in index coding. As before, suppose
we have a graph G(V = [n], E) on n vertices. We assume here that vertex i ∈ [n] stores Xi ∈ Fm
q , a q-ary
random vector of length m. We want the following repair criterion to be satisfied: if up to any δ, 0 ≤ δ ≤ 1,
proportion of the m coordinates of Xi , i ∈ [n] are erased, they can be recovered by using the remaining
content of the vertex i and XN (i) , the contents in the neighbors of the vertex.
We call the normalized asymptotic maximum total amount of information (in terms of q-ary unit)
lim

m→∞

H(X1 , X2 , . . . , Xn )
,
m

that can be stored in the graph G, to be the partial recovery capacity of G. This is denoted by Capq (G, δ).
11

(a) Graph G. Shaded vertices are X = SX .

(b) Graph G[Y ]. Shaded vertices are SY .

Figure 3: Example of a storage capacity proof for cycles with chords. See text for details.

We have the following simple facts.
Proposition 8. For a graph G, Capq (G, 0) = n and Capq (G, 1) = Cap(G).
Proof. The first statement is quite evident. For the second, note that,
Capq (G, 1) = lim Capqm (G) = sup Capqm (G) = Cap(G),
m→∞

m

where we could use the lim and the sup interchangeably since Capqm (G) is a nondecreasing and bounded
sequence in m.
In the remaining parts of this section, we will provide tight upper and lower bound on the quantity
Capq (G, δ).

5.1

Impossibility bound

Note that, the partial recovery capacity can be defined in terms of an entropy maximization problem,
generalizing the storage capacity.
Theorem 9. Let H(X) be the entropy of X measured in q-ary units. Suppose, Xi ∈ Fm
q , i ∈ [n]. For a
graph G([n], E), Capq (G, δ) is upper bounded by the solution of the following optimization problem.
max lim

m→∞

H(X1 , . . . , Xn )
,
m

(8)

such that,
H(Xi | XN (i) ) ≤ logq Aq (m, δm + 1),
where Aq (m, d) is the maximum possible size of a q-ary m-length error-correcting code with minimum
distance d.

12

Proof. Let Xi ∈ Fm
q , i ∈ [n] be the random variables that can be stored in the vertices of G satisfying the
repair condition. Suppose we are given the values of XN (i) . In this situation let M ⊆ Fm
q be the set of
possible values of Xi (P (Xi = a) > 0, ∀a ∈ M ). Let Xi1 , Xi2 be any two different elements of M . We
claim that, the Hamming distance between Xi1 , Xi2 is at least δm + 1, or
d(Xi1 , Xi2 ) ≥ δm + 1.
Suppose this is not true. Then there exist Xi1 , Xi2 ∈ M such that d(Xi1 , Xi2 ) ≤ δm. Let J ⊂ {1, . . . , m} be
the coordinates where Xi1 and Xi2 differ. Therefore, |J| ≤ δm. Suppose Xi1 was stored in vertex i and the
coordinates in J are erased. Now, there will not be any way to uniquely identify Xi : it can be either of Xi1 or
Xi2 . Hence the repair condition will not be satisfied which is a contradiction.
Therefore, M ⊆ Fm
q is a set of vectors such that any two elements of M is Hamming distance at
least δm + 1 apart. Hence M is an error-correcting code with minimum distance δm + 1. And therefore,
|M | ≤ Aq (m, d). This implies, H(Xi | XN (i) ) ≤ logq Aq (m, δm + 1), which proves the theorem.
Let us define
Rq (δ) ≡ lim

m→∞

Aq (m, δm + 1)
,
m

assuming the limit exists.
Corollary 10. We must have, for any graph G, Capq (G, δ) = Cap(G) for δ ≥ 1 − 1q . In particular,
Cap2 (G, δ) = Cap(G) for δ ≥ 12 .
The proof of this fact follows since Rq (δ) = 0 for δ ≥ 1 − 1q .
Generalizing the technique of upper bounding the storage capacity via an information theoretic linear
program, we can obtain an upper bound on Capq (G, δ). We define a variable zS for every S ⊆ V and let
bo(S, T ) = (cl(S) \ S) ∩ T denote the boundary of the set S consisting of vertices in T with all neighbors
in S. Our main upper bound is the following.
Theorem 11. Consider the LP below.
maximize

zV

s.t. z∅ = 0
zT − zS ≤ |T \ S| − (1 − Rq (δ)) bo(S, T ) ∀S ⊆ T
zS + zT ≥ zS∩T + zS∪T

∀S, T

The optimal solution to the above LP is an upper bound on Capq (G, δ).
We omit the proof here since it is exactly same as the proof of the bound via information theoretic LP of
Sec. 4.1.
5.1.1

Odd cycle

Consider an odd cycle with n vertices (n is odd). Below we show an example to illustrate the above bound
on partial recovery capacity.

13

Consider the following subset of constraints:
2 ≥ z{1,3} − z∅
2 ≥ z{2,4} − z∅
1 ≥ z{i}

∀i ∈ {5, 6, . . . , n}

Rq (δ) ≥ z{1,2,3} − z{1,3}
Rq (δ) ≥ z{2,3,4} − z{2,4}
z{1,2,3} + z{2,3,4} ≥ z{2,3} + z{1,2,3,4}
n−3
z
z{2,3} + z{5} + z{7} + · · · + z{n} ≥ z{2,3,5,7,...,n} +
2 ∅
n−5
z
z{1,2,3,4} + z{6} + z{8} + . . . z{n−1} ≥ z{1,2,3,4,6,8,...,n−1} +
2 ∅
n+1
n−1
(n −
) − (1 − Rq (δ))
≥ zV − z{2,3,5,7,...,n}
2
2
n−3
n+3
) − (1 − Rq (δ))
≥ zV − z{1,2,3,4,6,8,...,n−1}
(n −
2
2

(a)
(b)

Equations (a) and (b) above are repeated applications of the inequality: zS + zT ≥ zS∪T + z∅ if S ∩ T = ∅.
By summing up those constraints we get
n + 2Rq (δ) + Rq (δ)(n − 2) ≥ 2zV − 2z∅
and thus
Capq (G, δ) ≤ zV ≤

n
(1 + Rq (δ)),
2

whenever G is an odd cycle.

5.2

Achievability bound

A naive achievability bound on Capq (G, δ) is given by,
Capq (G, δ) ≥ n(1 − hq (δ)),

1
δ≤ ,
2

where hq (x) ≡ x logq (q − 1) − x logq x − (1 − x) logq (1 − x). This amount of storage can be achieved by
just using an error-correcting code of length m, distance δm + 1, and rate 1 − hq (δ) in each of the vertices.
Such codes exist, by the Gilbert-Varshamov bound. Also,
Capq (G, δ) ≥ 0,
for 0 ≤ δ ≤ 1 − 1q .
This simple bound can be improved by more carefully designing a code. Our main result of this section is
the following.
Theorem 12. Given a graph G, let C be the set of all cliques of G. The generalized clique packing number
CPδ (G) is defined to be the optimum of the following linear program. For 0 ≤ xC ≤ 1, ∀C ∈ C,
X
max
xC (|C| − hq (δ)),
C∈C

14

such that,
X

xC ≤ 1.

C∈C:u∈C

Then,
Capq (G, δ) ≥ CPδ (G),

1
δ ≤1− ,
q

Capq (G, δ) ≥ CP(G),

1
δ >1− .
q

and,

Proof. We illustrate the proof of this theorem by constructing a sequence of error-correcting codes that serves
our purpose.
Let us first find a maximum matching M ⊆ E of the graph. Now for each edge (u, v) ∈ M use a q-ary
error-correcting code of length 2m that can correct any δm erasures in the first m coordinates and any δm
erasures in the second m coordinates.
We claim that such error-correcting code of length 2m and dimension 2m − mhq (δ) exists.
Randomly and uniformly choose a q-ary parity check matrix of size (2m − k) × 2m (that is, each
coordinate of the matrix is chosen from {0, 1, . . . , q − 1} with uniform probability). The probability that a
vector of weight δm is a codeword is q −(2m−k) . Now the probability that there exists such a codeword that is
an uncorrectable erasure pattern of the above type is
 
m
1
≤2
(q − 1)δm q −(2m−k) ∼ q −(2m−k−mhq (δ)) , δ ≤ 1 − .
δm
q
Hence there exists such a code with dimension = 2m − mhq (δ). Therefore the total number of q-ary numbers
that can be stored is
|M | · (2m − mhq (δ)) = m · MM(G)(2 − hq (δ)),
where MM(G) is a maximum matching in G. Hence,
Capq (G, δ) ≥ MM(G)(2 − hq (δ)),

1
δ ≤1− .
q

For δ ≥ 1 − 1q , Capq (G, δ) ≥ MM(G).
Following an argument similar to Lemma 1, it is possible to improve the maximum matching argument
here to the fractional maximum matching. Therefore, we must have,
Capq (G, δ) ≥ FM(G)(2 − hq (δ)),

1
δ ≤1− ,
q

and, or δ ≥ 1 − 1q , Capq (G, δ) ≥ FM(G), where FM(G) denote the size of the maximum fractional
matching of G.
The above argument can easily be extended towards clique packing instead of maximum matching. If we
have a clique of size L, then we need to choose a code of length Lm. We again, randomly and uniformly
choose a q-ary parity check matrix of size (Lm − k) × Lm. The probability that a vector of weight δm is a
codeword is q −(Lm−k) . Now the probability that there exists such a codeword that is an uncorrectable erasure
pattern of the above type is
 
m
1
≤L
(q − 1)δm q −(Lm−k) ∼ q −(Lm−k−mhq (δ)) , δ ≤ 1 − .
δm
q
15

Therefore there exists a good code of dimension Lm − mhq (δ). Using this code, total number of q-ary
integers that can be stored is m CPδ (G), by following the argument of Lemma 1. This proves the claim.
Example - Odd Cycle: Let us consider the example of n-cycle again where n is an odd number. Since the
size of a fractional matching is n2 , we have
Capq (G, δ) ≥
and Capq (G, δ) ≥

n
2

n
(2 − hq (δ)),
2

1
δ ≤1− ,
q

when δ > 1 − 1q . Compare this with the impossibility bound that we have,
Capq (G, δ) ≤

n
(1 + Rq (δ)).
2

It is widely conjectured that the optimal rate of an error-correcting code is given by
Rq (δ) = 1 − hq (δ),
for small q, which is also known as the Gilbert-Varshamov conjecture. If this conjecture is true, then our
upper and lower bounds match exactly. In particular, for large q (i.e., q → ∞), we have hq (δ) → δ and
Rq (δ) → 1 − δ. Hence, our bounds match definitively in the regime of large q.

References
[1] N. Alon and A. Orlitsky. Source coding and graph entropies. IEEE Transactions on Information Theory,
42(5):1329–1339, 1996.
[2] K. Appel and W. Haken. Every planar map is four colorable. part i: Discharging. Illinois J. Math., 21(3):429–490,
09 1977.
[3] K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. part ii: Reducibility. Illinois J. Math.,
21(3):491–567, 09 1977.
[4] B. S. Baker. Approximation algorithms for np-complete problems on planar graphs. J. ACM, 41(1):153–180,
1994.
[5] R. Bar-Yehuda and S. Even. On approximating a vertex cover for planar graphs. In Proceedings of the 14th Annual
ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 303–309, 1982.
[6] Z. Bar-Yossef, Y. Birk, T. Jayram, and T. Kol. Index coding with side information. IEEE Transactions on
Information Theory, 57(3):1479–1494, 2011.
[7] Y. Berliner and M. Langberg. Index coding with outerplanar side information. In Information Theory Proceedings
(ISIT), 2011 IEEE International Symposium on, pages 806–810. IEEE, 2011.
[8] A. Blasiak, R. Kleinberg, and E. Lubetzky. Lexicographic products and the power of non-linear network coding.
In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA,
October 22-25, 2011, pages 609–618, 2011.
[9] A. Blasiak, R. D. Kleinberg, and E. Lubetzky. Index coding via linear programming. CoRR, abs/1004.1379, 2010.
[10] R. Bowden, H. X. Nguyen, N. Falkner, S. Knight, and M. Roughan. Planarity of data networks. In Teletraffic
Congress (ITC), 2011 23rd International, pages 254–261. IEEE, 2011.

16

[11] M. Effros, S. El Rouayheb, and M. Langberg. An equivalence between network coding and index coding. IEEE
Transactions on Information Theory, 61(5):2478–2487, 2015.
[12] M. Gadouleau, A. Richard, and S. Riis. Fixed points of boolean networks, guessing graphs, and coding theory.
SIAM Journal on Discrete Mathematics, 29(4):2312–2335, 2015.
[13] P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin. On the locality of codeword symbols. IEEE Transactions on
Information Theory, 58(11):6925–6934, 2012.
[14] H. Grötzsch. Zur theorie der diskreten gebilde, vii: Ein dreifarbensatz fr dreikreisfreie netze auf der kugel. Wiss.
Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe, 8:109120, 1959.
[15] S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2- ε. Journal of Computer and System
Sciences, 74(3):335–349, 2008.
[16] M. Langberg and A. Sprintson. On the hardness of approximating the network coding capacity. IEEE Transactions
on Information Theory, 57(2):1008–1014, 2011.
[17] A. Mazumdar. Storage capacity of repairable networks. IEEE Transactions on Information Theory, 61(11):5810–
5821, 2015.
[18] C. Shannon. The zero error capacity of a noisy channel. IRE Transactions on Information Theory, 2(3):8–19,
1956.

17

