Coded Caching as Structured Index Coding

Why the MAN Conflict Graph Is Easy

We have seen that general index coding is NP-hard. We have also seen that the MAN scheme achieves rate (Kβˆ’t)/(t+1)(K - t)/ (t + 1), exactly matching the LP lower bound on the induced index coding instance.

Why does this work for MAN instances but not for general graphs? The answer is a matter of symmetry. The MAN conflict graph is vertex-transitive β€” any vertex can be mapped to any other by an automorphism of the graph (coming from the symmetric group's action on [K][K]). For vertex-transitive graphs, the LP bound is tight and computable. This is the hidden combinatorial gift of the MAN placement.

Definition:

The MAN Conflict Graph

For MAN coded caching with parameters (K,N,M)(K, N, M), t=KM/Nt = K M/ N, and demand vector d∈[N]K\mathbf{d} \in [N]^K with all distinct entries, the MAN conflict graph GMAN(K,t,d)G_{\text{MAN}}(K, t, \mathbf{d}) has:

  • V={(k,T):k∈[K],TβŠ†[K]βˆ–{k},∣T∣=t}V = \{(k, \mathcal{T}) : k \in [K], \mathcal{T} \subseteq [K]\setminus\{k\}, |\mathcal{T}| = t\} β€” one vertex per missing-subfile pair.
  • Edge {(k,T),(kβ€²,Tβ€²)}\{(k, \mathcal{T}), (k', \mathcal{T}')\} iff Tβˆͺ{k}β‰ Tβ€²βˆͺ{kβ€²}\mathcal{T} \cup \{k\} \neq \mathcal{T}' \cup \{k'\} (i.e., the two missing subfiles do not belong to the same (t+1)(t+1)-subset delivery group).

The graph has Kβ‹…(Kβˆ’1t)K \cdot \binom{K-1}{t} vertices.

Theorem: Structural Properties of the MAN Conflict Graph

The MAN conflict graph GMAN(K,t)G_{\text{MAN}}(K, t) satisfies:

  1. Vertex-transitivity: the symmetric group SKS_K acts transitively on VV.
  2. Independence number: Ξ±(GMAN)=t+1\alpha(G_{\text{MAN}}) = t + 1.
  3. Chromatic number: Ο‡(GMAN)=(Kt+1)\chi(G_{\text{MAN}}) = \binom{K}{t+1}.
  4. Size of each color class: t+1t + 1, matching the number of users served per XOR.
  5. Rate: Ξ²(GMAN)=Ο‡(GMAN)/(Kt)=(Kβˆ’t)/(t+1)\beta(G_{\text{MAN}}) = \chi(G_{\text{MAN}})/\binom{K}{t} = (K-t)/(t+1) in normalized file units.

The automorphism group acts transitively (you can relabel users freely). The maximum independent set corresponds to one (t+1)(t+1)-subset (all subfiles missing by users in a single delivery group). A proper coloring with (Kt+1)\binom{K}{t+1} colors assigns each (t+1)(t+1)-subset a distinct color β€” one per coded XOR message.

Proof
Vertex-transitivity

For any two vertices (k,T)(k, \mathcal{T}) and (kβ€²,Tβ€²)(k', \mathcal{T}'), find a permutation Ο€βˆˆSK\pi \in S_K with Ο€(k)=kβ€²\pi(k) = k' and Ο€(T)=Tβ€²\pi(\mathcal{T}) = \mathcal{T}'. Such Ο€\pi exists because both pairs have the same "type" (∣T∣=∣Tβ€²βˆ£=t|\mathcal{T}| = |\mathcal{T}'| = t, kβˆ‰Tk \notin \mathcal{T}, kβ€²βˆ‰Tβ€²k' \notin \mathcal{T}'). Apply Ο€\pi to the entire graph.

Independence number

An independent set is a set of vertices pairwise non-adjacent β€” i.e., all vertices share the same (t+1)(t+1)-subset. There are exactly t+1t+1 such vertices per subset (one per user k∈Sβ€²k \in \mathcal{S}'). Hence Ξ±=t+1\alpha = t+1.

Chromatic number

Partition VV into (Kt+1)\binom{K}{t+1} color classes, one per (t+1)(t+1)-subset Sβ€²\mathcal{S}'. Each color class is an independent set of size t+1t+1. This is a valid (Kt+1)\binom{K}{t+1}-coloring, and it's tight because Ο‡β‰₯∣V∣/Ξ±=K(Kβˆ’1t)/(t+1)=(Kt+1)\chi \geq |V|/\alpha = K\binom{K-1}{t}/(t+1) = \binom{K}{t+1}.

Rate

Each color class yields one XOR, normalized by subfile size 1/(Kt)1/\binom{K}{t}. Rate: (Kt+1)/(Kt)=(Kβˆ’t)/(t+1)\binom{K}{t+1}/\binom{K}{t} = (K-t)/(t+1) file units. β– \blacksquare

Key Takeaway

Coded caching works because the MAN placement creates a vertex-transitive conflict graph with perfect LP integrality. The delivery problem β€” usually NP-hard β€” becomes trivial: a balanced coloring with (Kt+1)\binom{K}{t+1} color classes, each of size t+1t+1. The MAN scheme is the unique (up to re-labeling) optimal index code for this graph.

Example: The MAN Graph for K=4K = 4, t=2t = 2

Construct GMAN(4,2)G_{\text{MAN}}(4, 2) explicitly and verify Ο‡(GMAN)=(43)=4\chi(G_{\text{MAN}}) = \binom{4}{3} = 4, matching the MAN rate Ξ²=4/(42)=4/6=2/3\beta = 4/\binom{4}{2} = 4/6 = 2/3.

Solution
Enumerate vertices

V={(k,T):k∈[4],TβŠ†[4]βˆ–{k},∣T∣=2}V = \{(k, \mathcal{T}) : k \in [4], \mathcal{T} \subseteq [4] \setminus \{k\}, |\mathcal{T}| = 2\}. For each kk, there are (32)=3\binom{3}{2} = 3 subsets, so ∣V∣=4Γ—3=12|V| = 4 \times 3 = 12.

Independent sets

Each (t+1)=3(t+1) = 3-subset Sβ€²βŠ†[4]\mathcal{S}' \subseteq [4] defines an independent set {(k,Sβ€²βˆ–{k}):k∈Sβ€²}\{(k, \mathcal{S}' \setminus \{k\}) : k \in \mathcal{S}'\} of size 3. There are (43)=4\binom{4}{3} = 4 such subsets, partitioning VV into 4 independent sets of size 3.

Coloring

Use these 4 independent sets as color classes: Ο‡(GMAN)≀4\chi(G_{\text{MAN}}) \leq 4. The lower bound Ο‡β‰₯4\chi \geq 4 follows from Ξ±=3\alpha = 3 and ∣V∣=12|V| = 12. Hence Ο‡=4\chi = 4 exactly.

Rate

4 coded messages, each of size 1/(42)=1/61/\binom{4}{2} = 1/6 files. Total rate: 4/6=2/34/6 = 2/3 files, matching the MAN formula RMAN(t=2)=(4βˆ’2)/(2+1)=2/3R_{\text{MAN}}(t = 2) = (4-2)/(2+1) = 2/3. βœ“

Graph-Coloring Delivery Schemes (Ch 14 Preview)

The graph-theoretic perspective of this chapter bears particular fruit in Chapter 14, where we design polynomial-subpacketization delivery schemes via explicit graph constructions. Placement Delivery Arrays (PDAs; Yan et al. 2017) and graph-coloring-based schemes (Kaji et al. 2020; CommIT authors in multi-antenna extensions) are all instantiations of the same principle: design a placement whose conflict graph admits a small-size coloring via a concrete combinatorial construction. The gap between MAN's (Kt)\binom{K}{t} subpacketization and these polynomial alternatives is the single largest practical obstacle the graph-coloring approach addresses.

Greedy Coloring of the MAN Conflict Graph

For K=4K = 4, t=1t = 1: the 12-vertex MAN conflict graph is colored with 4 colors, each representing one XOR delivery message. The balanced coloring (each class of size 3) matches the MAN rate R=(Kβˆ’t)/(t+1)=3/2=1.5R = (K-t)/(t+1) = 3/2 = 1.5 file units.

Why This Matters: Index Coding and Interference Alignment

Maleki, Cadambe, and Jafar (2014) showed that the asymptotic index coding rate equals the symmetric interference alignment (IA) rate for the corresponding linear BC. This connects index coding β€” an apparently discrete combinatorial problem β€” to the continuous linear-precoding literature in wireless communications. For cache-aided MIMO BC (Ch 5), the IA perspective is essential: Lampiris, Caire, et al. use it to derive the DoF=t+L\mathrm{DoF} = t + L result.

Historical Note: Index Coding: From Bit-Cache to Network Tool

1998–2014

The index coding problem has grown in scope since Birk and Kol introduced it in 1998. A partial history:

  • 1998: Birk-Kol "Informed-Source Coding On Demand" β€” original formulation.
  • 2011: Bar-Yossef et al. β€” minrank characterization and linear code rate.
  • 2008–2014: Alon et al., Lubetzky-Stav β€” gaps between linear and non-linear codes, connections to Kneser graphs.
  • 2014: Maddah-Ali & Niesen β€” coded caching is index coding with designed side information.
  • 2014: Maleki-Cadambe-Jafar β€” index coding vs interference alignment equivalence.
  • 2017–present: Arbabjolfaei, Kim, and collaborators β€” ongoing study of exact broadcast rates for small graphs; connections to network coding and distributed storage.

The coded caching perspective β€” design the side information to make the problem easy β€” has reinvigorated index coding research. Before 2014 the problem was viewed as a pathology: hopelessly hard, interesting only for theorists. Coded caching showed it can be a design primitive, not just an analysis tool.

NP-Hardness and Practical HeuristicsChapter Summary