Lossless clique compression and provable guarantees for minrank computation in index coding

The optimal scalar linear index code for a single-unicast index coding problem equals the minrank of its side-information graph, a quantity that is NP-hard to compute and, by recent results, NP-hard to approximate within any constant factor. Vaddi and Rajan (2019) proposed a field-size-independent heuristic pipeline for this computation: delete minrank-non-critical edges, compress a clique partition of the graph into a smaller graph $G_R$, and assemble an index code from a heuristic clique cover. The paper proves only a sufficient condition (Lemma 6) under which the compression step preserves minrank exactly and provides no performance guarantees for its heuristic clique-cover algorithm or its overall construction. The goal is threefold: to settle a full necessary-and-sufficient characterization of when clique compression preserves minrank together with the graph classes on which the reduction steps are minrank-preserving beyond the sufficient conditions the paper proves; to obtain provable worst-case guarantees (approximation ratios or optimality conditions) for the paper's constructions; and to design algorithms that compute or bound minrank more efficiently than the paper's heuristics within the known complexity barriers.

Background

In the index coding problem, a broadcaster holds $n$ messages and serves receivers, each of which already knows some subset of the messages (its side information) and demands another subset; the goal is to minimize the number of broadcast symbols from which every receiver can decode its demand. In a single-unicast index coding problem each receiver demands exactly one message and the demands are distinct, so the instance is described by a directed side-information graph $G$ on the messages, with an edge $i \to j$ meaning the receiver demanding message $i$ knows message $j$. A scalar linear index code over a field $\mathbb{F}_q$ encodes the $n$ messages into $\ell$ symbols by a linear map, and its optimal length equals the minrank $\operatorname{minrank}(G)$: the minimum rank of a fitting matrix, i.e., a matrix over $\mathbb{F}_q$ that is unconstrained on the diagonal and on edge positions and zero on non-edge positions (Haemers 1979; Bar-Yossef, Birk, Jayram, and Kol 2011). Because this rank is taken over $\mathbb{F}_q$, minrank is field-parameterized — write $\operatorname{minrank}_q(G)$ — and is not in general the same over different fields. The construction and reductions studied below are binary: they assume a finite field of characteristic $2$, and the results extend to fields of any characteristic, so characterizations and guarantees for that pipeline are to be read over a field of characteristic $2$; the field-general approximation factors cited below, by contrast, hold for $\operatorname{minrank}_q$ over any fixed finite field $\mathbb{F}_q$. Two classical bounds sandwich the optimum: the clique cover number of $G$ (serve each clique with one XOR transmission) is an upper bound on $\operatorname{minrank}(G)$, and the maximum acyclic induced subgraph $\operatorname{MAIS}(G)$ is a lower bound. Computing minrank is NP-hard (Peeters 1996), which makes certified, efficient procedures the central algorithmic challenge. The minrank parameter also governs the general groupcast setting (receivers may demand overlapping sets of messages), where the side information is a hypergraph; a groupcast instance can be converted to a single-unicast one at the cost of a larger graph.

Against this background, Vaddi and Rajan (2019) proposed a heuristic, field-size-independent pipeline for constructing index codes — field-size independent in that it uses only binary XOR operations and so avoids the large field sizes required by alternative methods such as low-rank matrix completion or partition multicast. The pipeline has four parts. (1) Minrank-non-critical edges — edges whose removal provably does not change the minrank — are identified and deleted: Lemma 4 shows that all edges incident to a vertex lying on no directed cycle are minrank-non-critical, and Theorems 2 and 3 show the same for all edges between two cliques of a clique partition of $V(G)$ that are cycle-free as a pair — in the sense of the paper's Definition 2, cliques $C_i$ and $C_j$ are cycle-free if there exist vertices $x_k \in C_i$ and $x_{k'} \in C_j$ such that no directed cycle consists of vertices only from a non-trivial subset of $\{x_k, x_{k'}\}$ together with vertices of $V(G) \setminus (C_i \cup C_j)$, a condition weaker than requiring that no directed cycle pass between the two cliques and one that is decidable in polynomial time once the two cliques are given; Theorem 3's reduction procedure applies these inter-clique deletions, reducing $G$ to a graph $\tilde{G}$ with $\operatorname{minrank}(G) = \operatorname{minrank}(\tilde{G})$. (2) Construction I then compresses a clique partition of $\tilde{G}$: each clique $C_i$ is merged into a single vertex $y_i$, with an edge $y_i \to y_j$ introduced exactly when all $|C_i| \cdot |C_j|$ directed edges from $C_i$ to $C_j$ are present, producing a graph $G_R$ with $\operatorname{minrank}(G) \le \operatorname{minrank}(G_R)$, so an index code for $G_R$ yields one for $G$ but possibly of strictly larger length (their Example 8); Lemma 6 proves that if every pair of cliques in the partition is cycle-free, then $\operatorname{minrank}(G) = \operatorname{minrank}(G_R)$. (3) Algorithm 1 heuristically finds a clique cover via binary operations on the adjacency matrix, combined with a cycle-cover step. (4) Construction II chains the groupcast-to-single-unicast conversion (Theorem 4), Algorithm 1, and Construction I into a polynomial-time, binary-field code construction of not necessarily optimal length. The authors state explicitly that the necessary and sufficient conditions under which Construction I preserves minrank "need further investigation" and that "both partition multicast and Construction II are suboptimal in the length of index code", and their conclusion asks to "analyze more properties of minrank and design algorithms to compute the minrank of a side-information graph in a more efficient way" — from which the systematic identification of graph classes on which the deletion rules are safe remains an open, only partially answered task.

Independently of this one pipeline, the general algorithmic landscape has since sharpened: Chawin and Haviv (2023) proved it is NP-hard to approximate minrank over finite fields within any constant factor, while Chawin and Haviv (2024) gave polynomial-time algorithms approximating the index coding rate — and every graph quantity sandwiched between the independence number and the clique cover number, with the Haemers minrank parameter explicitly among those covered — to within $O(n/\log^2 n)$ for $n$-vertex (undirected) graphs and $O(n/\log n)$ for directed graphs, improving the $O(n/\log n)$ guarantee for graphs of Blasiak, Kleinberg, and Lubetzky (2013); Golovnev, Regev, and Weinstein (2018) showed that on Erdős–Rényi random graphs $G(n,p)$ with constant $p$ the minrank is $\Theta(n/\log n)$ with high probability, matching the clique-cover upper bound. None of these general results analyzes the specific compression-and-deletion machinery of Vaddi and Rajan.

Problem Statement

The problem originates in the open items and acknowledged gaps of Vaddi and Rajan (2019): convert their heuristic, field-size-independent minrank-reduction and index-code-construction pipeline into a certified one, with three components sharing one objective, each independently standing: (1) Compression correctness: find necessary and sufficient conditions on a side-information graph $G$ (equipped with the clique partition used by Construction I after the minrank-non-critical edge deletions) under which the clique compression of Construction I is lossless, i.e., $\operatorname{minrank}(G) = \operatorname{minrank}(G_R)$; Lemma 6's condition — every pair of cliques in the partition is cycle-free in the sense of Definition 2 (see Background) — is known to be sufficient only, and the paper states that the full characterization needs further investigation. This includes the companion task of characterizing the minrank-non-critical edges strictly beyond the paper's sufficient conditions, that is, deciding whether removing an edge to which Lemma 4 and Theorems 2–3 do not apply still leaves the minrank unchanged, and systematically identifying the graph classes on which such additional deletions are minrank-preserving. (2) Construction quality — this component concretizes a gap the authors themselves acknowledge, since they note that "both partition multicast and Construction II are suboptimal in the length of index code" without themselves posing a guarantee question: quantify the worst-case performance of the heuristic parts of the pipeline — the clique-cover Algorithm 1 and the end-to-end groupcast construction (Construction II) — by proving approximation ratios for the produced index code length relative to the optimum $\operatorname{minrank}$ over the field of the construction, or conditions under which the constructions are optimal — where the clique-cover step is heuristic because optimal clique cover is NP-hard. (3) Efficiency: design algorithms that compute (or bound) the minrank of a side-information graph more efficiently than the presented heuristics, in any form compatible with the known barriers — exact computation is NP-hard (Peeters) and constant-factor approximation is NP-hard (Chawin–Haviv 2023) — such as polynomial-time exact algorithms for delimited graph classes, certified lossless reductions of the Construction-I type, or approximations improving on the currently best factors of $O(n/\log^2 n)$ for undirected graphs and $O(n/\log n)$ for directed graphs. The common objective across all components is a minrank-computation methodology for index coding whose reductions are certified lossless on a precisely characterized domain and whose remaining approximation loss carries a provable worst-case bound.

References

1. Mahesh Babu Vaddi and B. Sundar Rajan, "A Field-Size Independent Code Construction for Groupcast Index Coding Problems", arXiv:1901.00164 (2019); published at 2019 IEEE Information Theory Workshop (ITW), DOI 10.1109/ITW44776.2019.8989347, https://arxiv.org/abs/1901.00164
2. René Peeters, "Orthogonal representations over finite fields and the chromatic number of graphs", Combinatorica 16(3):417–431 (1996), DOI 10.1007/BF01261326, https://doi.org/10.1007/BF01261326
3. W. Haemers, "On Some Problems of Lovász Concerning the Shannon Capacity of a Graph", IEEE Transactions on Information Theory 25(2):231–232 (1979), DOI 10.1109/TIT.1979.1056027, https://doi.org/10.1109/TIT.1979.1056027
4. Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, "Index Coding With Side Information", IEEE Transactions on Information Theory 57(3):1479–1494 (2011), DOI 10.1109/TIT.2010.2103753, https://doi.org/10.1109/TIT.2010.2103753
5. Anna Blasiak, Robert Kleinberg, and Eyal Lubetzky, "Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate", IEEE Transactions on Information Theory 59(9):5811–5823 (2013), DOI 10.1109/TIT.2013.2264472, https://doi.org/10.1109/TIT.2013.2264472
6. Dror Chawin and Ishay Haviv, "Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank", SIAM Journal on Discrete Mathematics 37(4):2670–2688 (2023), DOI 10.1137/23m155760x, https://doi.org/10.1137/23m155760x (preliminary version in STACS 2023; arXiv:2301.00732)
7. Dror Chawin and Ishay Haviv, "Improved Approximation Algorithms for Index Coding", IEEE Transactions on Information Theory 70(11):8266–8275 (2024), DOI 10.1109/TIT.2024.3446000, https://doi.org/10.1109/TIT.2024.3446000 (arXiv:2408.08382)
8. Dror Chawin and Ishay Haviv, "Hardness of Linear Index Coding on Perturbed Instances", IEEE Transactions on Information Theory 70(2):1388–1396 (2024), DOI 10.1109/TIT.2023.3347296, https://doi.org/10.1109/TIT.2023.3347296
9. Alexander Golovnev, Oded Regev, and Omri Weinstein, "The Minrank of Random Graphs", IEEE Transactions on Information Theory 64(11):6990–6995 (2018), DOI 10.1109/TIT.2018.2810384, https://doi.org/10.1109/TIT.2018.2810384 (arXiv:1607.04842)
10. Mehrdad Tahmasbi, Amirbehshad Shahrasbi, and Amin Gohari, "Critical Graphs in Index Coding", IEEE Journal on Selected Areas in Communications 33(2):225–235 (2015), DOI 10.1109/JSAC.2014.2384294, https://doi.org/10.1109/JSAC.2014.2384294
11. Niranjana Ambadi, "Unicast-Uniprior Index Coding Problems: Minrank and Criticality", arXiv:1901.04926 (2019), DOI 10.48550/arXiv.1901.04926, https://arxiv.org/abs/1901.04926
12. Anjana A. Mahesh and B. Sundar Rajan, "Minrank of Embedded Index Coding Problems and its Relation to Connectedness of a Bipartite Graph", arXiv:2201.08680 (2022), DOI 10.48550/arXiv.2201.08680, https://arxiv.org/abs/2201.08680