Index coding via linear programming

1 Introduction

• The problem asks for an encoding scheme that minimizes broadcast length while allowing each receiver to decode its requested message from the transmission and side information.The asymptotic broadcast rate β is the average number of broadcast bits per input bit for long messages.Source: §1 · pp. 1–2

1.1 History of the problem

• Prior work bounded β indirectly through graph parameters and related capacities, but its exact value was unknown beyond cases where α(G) and χ(G) coincide.No polynomial-time algorithm was known to approximate β better than the trivial factor n by more than a constant factor.Source: §1.1 · pp. 2–3

1.2 New techniques for bounding and approximating the broadcast rate

• The paper introduces a hierarchy of n information-theoretic linear programs with values b1 ≤ b2 ≤ ... ≤ bn, satisfying b2 ≤ β ≤ bn, with both inequalities potentially strict.For graphs, the extreme solutions connect to graph parameters, including the independence number and fractional clique-cover number.Source: §1.2 · p. 3
• The resulting methods provide a polynomial-time approximation algorithm for general broadcasting instances and a polynomial-time procedure for deciding whether β(G)=2.The approximation also extends to weighted messages with different rates.Source: §1.2 · p. 4

1.3 Consequences for graphs

• The LP bounds determine β exactly for graph families including cycles and cycle-complements, with β(Cn)=n/2 and β(C̅n)=n/⌊n/2⌋.For the 5-cycle, the result closes the gap between b2(C5)=2.5 and β*=5−log2 5≈2.68.Source: §1.3 · p. 4
• The constructions yield a linear gap between scalar and vector capacities, including graphs with β=n/2 and α=2, and graphs with β=3 while clique-cover schemes cost χf(G)=Θ(n^1/4).Thus β can remain uniformly bounded while clique-cover-based upper bounds are polynomially larger.Source: §1.3 · pp. 4–5

2.3 The broadcast rate of the 5-cycle

• The LP method determines β(C5)=5 and extends to exact broadcast-rate results for cycles, their complements, and other graph families.When b2 equals χf, the common value determines β; the section presents C5 as a proof-by-picture example and points to later family results.Source: §2 · p. 5, §2.3 · p. 10, Figure 1 · p. 11

2.1 The LP hierarchy

• The LP hierarchy uses decoding and information-theoretic inequalities to lower-bound β, while its final level yields an upper bound through fractional hyperclique covers.For graphs, bn equals the fractional clique-cover number; for general broadcasting networks, the analogous parameter is the strong fractional hyperclique-cover number.Source: §2.1 · pp. 5–7

2.2.1 Bounding the broadcast rate via the LP hierarchy

• b1(G)=α(G) for graphs, identifying the first LP level with the independence number.The equality follows by constructing feasible LP solutions from maximum independent sets and using the decoding, initialization, and slope constraints.Source: §2.1 · p. 6, §2.2.1 · p. 7
• b2(G)≤β(G), because any valid index code induces a feasible B2 solution whose objective value is the public-channel entropy.The induced LP function is X(S)=H(S,P), where P is the public transmission and H(P)=β.Source: §2.2.1 · p. 8
• β(G)≤bn(G)=χf(G), with χf defined as the minimum size of a strong fractional hyperclique-cover.The upper bound is realized by converting a fractional cover into a vector index code, while the nth-order submodularity constraints characterize weighted coverage functions.Source: §2.2.1 · pp. 8–9

2.2.2 Strict lower and upper bounds for the broadcast rate

• The hierarchy can be strict: one three-message instance has β(G)≤2 but b3(G)≥3, so β(G)<b3(G)≤bn(G).The construction uses receivers ({a},b), ({b},c), and ({c},a), with a⊕b and b⊕c as a valid two-symbol solution.Source: §2.1 · p. 7, §2.2.2 · p. 10

2.4 Corollaries for vector/scalar index codes

• Odd cycles with n≥5 and their complements provide graphs where α<β; specifically, C5 has α=2 and β=5.These are presented as the first such graph examples before this work and its companion paper.Source: §2.3 · p. 10, §2.4 · p. 10
• For the family G = k · C5 on n = 5k vertices, β(G) = n/2, α(G) = 2k, β1(G) = (1−1/5 log2 5+o(1))n ≈ 0.54n, and β∗(G) = (1−o(1))β1(G).Source: §2.4 · pp. 11–12
• The broadcast rate β and direct-sum capacity β∗ are additive under disjoint unions, while β ≤ β∗ ≤ β1.Additivity of β∗ follows through fractional-chromatic-number multiplicativity, and additivity of β is proved using blow-ups and limiting arguments.Source: §2.4 · pp. 11–12
• The linear separation between β and β1 can be transferred to Network Coding, producing instances where the vector-to-scalar-linear capacity ratio is precisely 1.2.The transfer uses a standard reduction from an n-vertex Index Coding graph to a capacitated Network Coding network on 2n + 2 vertices.Source: §2.4 · p. 12
• For k disjoint 5-cycles, the scalar-linear Index Coding capacity over any finite field equals 3k, using minrkF(C5) = 3 and additivity of minrkF.The bound minrkF(C5) ≤ χ(C5) = 3 comes from linear clique-cover encoding, while minrkF(C5) ≥ ⌈β(C5)⌉ = 3.Source: §2.4 · p. 12

3.1 Approximating the broadcast rate in general networks

• A polynomial-time approximation framework bounds β between the maximum expanding-sequence size α(G) and the minimum fractional weak hyperclique-cover weight ψ_f(G).Expanding sequences provide the lower bound β(G)≥α(G), while fractional weak hyperclique-covers provide β(G)≤ψ_f(G).Source: §3.1 · pp. 14, 16
• The algorithm either finds an expanding sequence of size k+1 or certifies ψ_f(G)≤6k·n^(1−1/k), using recursive partitioning and sampled hypercliques.The sampled-hyperclique construction gives ψ_f(G)≤4d+2 under the stated neighborhood condition, and the recursive lemma converts this into the stated bound.Source: §3.1 · p. 15

3.2 Extending the algorithm to networks with variable source rates

• The same approximation strategy extends to weighted hypergraphs with variable source rates by weighting hyperclique covers and expanding sequences, then applying a dyadic partition of vertices by rate.The weighted definitions preserve the earlier proofs except for the unweighted lemma, which is handled separately within each rate class and combined through the computable quantity τ(G).Source: §3.2 · pp. 16–17

3.3 Proof of Theorem 2, determining whether the broadcast rate equals 2

• For directed hypergraphs, β(G)=2 exactly when a G-compatible function exists, equivalently when the graph contains no almost alternating cycle; these conditions are decidable in polynomial time.Almost alternating cycles are the minimal obstruction used in the proof, and the characterization generalizes the bipartite criterion for undirected graphs.Source: §3.3 · p. 18
• An almost alternating cycle of length 2n+1 implies β(G) ≥ 2 + 1/n > 2 via summed entropy inequalities.The argument derives H(y) ≥ 2 + 1/n from decoding constraints and submodularity.Source: §3.3 · pp. 18–19
• If G has no almost alternating cycle, the transitive closure of receiver-side co-occurrence defines a G-compatible quotient map F.Vertices are related when they jointly occur in some receiver’s interference set; incompatibility would construct an almost alternating cycle.Source: §3.3 · p. 19
• The relation, quotient map, and compatibility test can all be computed in polynomial time.Source: §3.3 · p. 19
• A G-compatible map produces a two-symbol linear code over a finite field that lets each receiver decode its requested message.The receiver subtracts known-neighbor terms, leaving a nonzero coefficient on its desired message.Source: §3.3 · p. 19

4.1 Separating the broadcast rate from the extreme LP solution bn

• The projective-Hadamard separation strengthens earlier results by making χf unbounded, and even polynomially large in n, while β remains constant.The section frames this as a separation from the extreme LP solution bn = χf.Source: §4.1 · p. 20
• β = 3 while χf = Θ(n1/4) for an explicit family of projective-Hadamard graphs.The construction uses a rank-3 Gram-matrix representation to upper-bound β, while the fractional clique-cover number grows with n.Source: §4.1 · p. 20

4.2 Broadcast rates for triangle-free graphs

• Triangle-free graphs can satisfy χf ≥ n/2 while having broadcast rate β ≤ 3.The graphs arise from odd-subset families whose intersection-parity matrix has rank at most n over GF(2).Source: §4.2 · pp. 21–22
• The triangle-free construction requires an odd-subset family larger than 2n, with no three sets having pairwise odd intersections.A family of size at least 8n/3 supplies the needed intersection-parity structure.Source: §4.2 · p. 21

4.3 Graphs with a broadcast rate of nearly 2

• For every fixed ε > 0, complements of Kneser graphs have β ≤ 2 + ε but χ(G) ≥ (ε/2) log N.This extends the trivial β = 2 class to a richer family with nearly minimal broadcast rate and growing chromatic number.Source: §4.3 · p. 22

5.1 The broadcast rate of cycles and their complements

• For every n ≥ 4, β(Cn) = n/2 and β(Cn) = n/⌊n/2⌋ for the complement, with β1 = ⌈β⌉ and α = ⌊β⌋ in both cases.The 5-cycle is thereby settled exactly, closing the gap between earlier bounds.Source: §5.1 · p. 23
• The LP framework proves exact rates by constructing lower bounds from B2 that meet fractional-clique-cover upper bounds.For cycles, the proof combines decoding inequalities and submodularity; for cyclic Cayley graphs, cyclic symmetry makes translated slices share the same LP value.Source: §5.1 · p. 23, §5.2 · pp. 23–24

5.2 The broadcast rate of cyclic Cayley Graphs

• Every 3-regular cyclic Cayley graph of Zn has broadcast rate β = n/2.For the nontrivial divisible-by-four case, the LP B2 uses cyclic symmetry and a sequence of submodularity inequalities to prove b2 ≥ n/2.Source: §5.2 · pp. 24–25
• For the circulant graph generated by {±1, . . . , ±k}, β = n/(k + 1).The proof partitions the cycle into sections, applies a slice inequality repeatedly, and combines it with the initialization constraint.Source: §5.2 · pp. 24–26

5.3 The broadcast rate of specific small graphs

• The second LP level is tight for the listed small examples, including the Petersen, Grötzsch, and Chvátal graphs.The reported values are β = 5 for the Petersen graph, β = 11/2 for the Grötzsch graph, and β = 6 for the Chvátal graph.Source: §5.3 · p. 26

6 Coverage functions: a proof of Lemma 2.10

• A feasible vector X satisfies the coverage inequalities if and only if X(S) = |S| + Σ_{T:T⊄S} w(T) for nonnegative weights w(T).This is the central coverage-function representation established by Lemma 6.2.Source: §6 · pp. 27–28
• Complement-switching and induction establish equivalence between the alternating-sum inequalities and the LP constraints.The argument first exchanges T with R\T, removes the constant term when |R| ≥ 2, and then inducts on |Z|.Source: §6 · p. 27
• The proof writes the set-function relation as a matrix equation and reduces feasibility to nonnegativity of M^-1F.The matrix M is shown invertible, with its inverse obtained through Kronecker-product identities.Source: §6 · pp. 28–29
• The matrix proof identifies the required nonnegative weights through an explicit inverse whose entries are alternating signs indexed by subsets.This converts the algebraic criterion into the stated coverage inequalities.Source: §6 · p. 29

• A polynomial-time algorithm determines whether β = 2 for any broadcasting network, addressing a fundamental recognition problem.Source: §7 · p. 29
• The paper gives an efficient multiplicative o(n)-approximation algorithm for β in general broadcasting problems.Source: §7 · p. 29
• The largest possible gap between the lower bound b2 and broadcast rate β remains an explicit question, because b2 can be strictly smaller than β.Source: §7 · p. 29
• Projective-Hadamard graphs show that β can remain uniformly bounded while the naive upper bound bn is polynomially large.Source: §7 · p. 29
• The section leaves open whether determining β < C is hard or even decidable, and whether scalar capacity β1 becomes unbounded for these graphs as q grows.Source: §7 · p. 29