Completing the near-extreme min-rank classification of side-information digraphs: the value $n-2$ and min-rank two over nonbinary fields

The min-rank of a side-information digraph $D$ over a finite field $\mathbb{F}_q$ equals the length of an optimal scalar linear index code for the corresponding index-coding-with-side-information instance. Dau, Skachek, and Chee (ISIT 2012; IEEE Transactions on Information Theory 2014) classified graphs and digraphs of near-extreme min-rank, leaving two digraph entries open: the structural characterization of digraphs with min-rank $n-2$, and both the characterization and the decision complexity of digraph min-rank two over nonbinary fields. Later work resolved the neighboring entries — digraphs of min-rank $n-1$ over sufficiently large fields are exactly the digraphs of feedback vertex number one (Byrne–Calderini), and deciding min-rank two is NP-complete over $\mathbb{F}_2$ (Dau et al.) but polynomial over sufficiently large fields (via the almost-alternating-cycle condition of Blasiak–Kleinberg–Lubetzky together with the field-size bound of Maleki–Cadambe–Jafar) — leaving as the surviving open core: (a) the complete characterization of digraphs of order $n$ with min-rank $n-2$, for which only the sufficient condition $\tau(D)=2$ (feedback vertex number two) is known, together with the complexity of deciding $\operatorname{minrk}_q(D)\le n-2$, conjectured NP-hard; and (b) the complexity of deciding whether a digraph has min-rank two over fixed nonbinary fields such as $\mathbb{F}_3$, between the settled binary and large-field regimes.

Background

In the index coding with side information (ICSI) problem, a sender holds $n$ messages $x_1,\dots,x_n$ and broadcasts coded symbols to $n$ receivers, where receiver $i$ wants $x_i$ and already knows some subset of the other messages. The instance is encoded by a side-information digraph $D$ with an arc $(i,j)$ whenever receiver $i$ knows $x_j$. A scalar linear index code over a finite field $\mathbb{F}_q$ transmits linear combinations of the messages; its length equals the rank of the $n\times n$ matrix whose rows generate the transmissions. Decodability forces a pattern on this matrix: it must fit $D$, meaning every diagonal entry is nonzero and the entry $m_{ij}$ is zero whenever $i\ne j$ and $(i,j)$ is not an arc of $D$. The min-rank $\operatorname{minrk}_q(D)$ is the minimum rank of a matrix fitting $D$, and Bar-Yossef, Birk, Jayram, and Kol proved it equals the length of an optimal scalar linear index code over $\mathbb{F}_q$. The broadcast rate $\beta(D)$ — the optimum over all codes including nonlinear and vector ones — satisfies $\alpha(D)\le\beta(D)\le\operatorname{minrk}_q(D)$, where $\alpha(D)$ is the maximum number of vertices of an acyclic induced subgraph (the MAIS lower bound). Min-rank of (undirected) graphs goes back to Haemers, who used it as an upper bound on the Shannon capacity of a graph — the largest rate at which symbols can be sent with zero error over a noisy channel whose confusability pattern is described by the graph; Peeters proved that deciding whether a graph has min-rank at most $3$ is NP-complete, and characterized graphs of min-rank two as exactly the non-complete graphs whose complement is bipartite, a condition checkable in polynomial time.

Dau, Skachek, and Chee studied the extreme and near-extreme values of min-rank, which correspond to ICSI instances where optimal scalar linear coding saves none, one, two, or all but two transmissions. They proved: a digraph has min-rank $n$ if and only if it is acyclic; a digraph has min-rank two over $\mathbb{F}_2$ if and only if it is not complete and its complement is fairly $3$-colorable (a fair $k$-coloring of a digraph is a proper vertex coloring in which, in addition, all out-neighbors of each vertex receive one common color); and deciding whether $\operatorname{minrk}_2(D)=2$ is NP-complete. For undirected graphs they completed the table: min-rank $n-1$ holds exactly for stars (connected case), and min-rank $n-2$ exactly for connected graphs of order at least six whose maximum matching has size two and which avoid one explicit forbidden subgraph. For digraphs, however, the entries for min-rank $n-1$ and $n-2$ were left unknown, as was the complexity of the min-rank-two decision problem over nonbinary fields (their Open Problem I); they also conjectured that for digraphs the boundary between easy and hard values at the top of the range lies at $n-1$, i.e. that deciding $\operatorname{minrk}_q(D)\le n-2$ is NP-hard.

Subsequent work reshaped this landscape. Ong showed that whenever the feedback vertex number $\tau(D)$ — the minimum number of vertices whose deletion makes $D$ acyclic, equivalently $n-\alpha(D)$ — is at most two, scalar linear coding is optimal and $\operatorname{minrk}_q(D)=\beta(D)=n-\tau(D)$ over every field; the codes are simple cyclic sums. Byrne and Calderini then characterized, for $q>n$, the digraphs of min-rank $n-1$: exactly those with $\tau(D)=1$, decidable in polynomial time. On the low end, Maleki, Cadambe, and Jafar showed from an interference-alignment viewpoint that over a sufficiently large field (of size at least the number of alignment subsets, in particular $q\ge n$) deciding whether two transmissions suffice is polynomial, via the earlier Blasiak–Kleinberg–Lubetzky characterization of two-transmission feasibility by the absence of an almost-alternating cycle (a directed odd cycle-like obstruction of at least five vertices). Most recently, Haviv proved that for undirected graphs deciding $\operatorname{minrk}_F(G)\le n-k$ is polynomial for every constant $k$ (a fixed-parameter kernel result), explicitly extending the graph side of Dau–Skachek–Chee while leaving the directed case open. After these advances, exactly two entries of the digraph classification remain unresolved, stated below.

Problem Statement

Complete the last two unresolved entries of the Dau–Skachek–Chee classification of side-information digraphs by min-rank — the quantity equal to the length of an optimal scalar linear index code. Both parts concern the same object and jointly finish the structural and complexity map of digraph min-rank over the extreme values $1,2,n-2,n-1,n$ of its range.

(a) Characterize the digraphs $D$ of order $n$ with $\operatorname{minrk}_q(D)=n-2$ over every finite field $\mathbb{F}_q$. The known sufficient condition is $\tau(D)=2$ (feedback vertex number two), which forces min-rank $n-2$ over every field; determine whether it is also necessary — that is, whether every digraph of min-rank $n-2$ has $\tau(D)=2$ — and identify which digraphs with $\tau(D)\ge 3$ still achieve min-rank $n-2$. Settle the computational complexity of deciding whether $\operatorname{minrk}_q(D)\le n-2$ (equivalently, whether scalar linear coding can save two transmissions), which Dau–Skachek–Chee conjecture to be NP-hard as the easy/hard threshold of digraph min-rank at the top of the range: deciding the values $n$ and $n-1$ is polynomial, and hardness is conjectured to begin at $n-2$.

(b) Settle the complexity of the decision problem 'does a given digraph have min-rank two over $\mathbb{F}_q$' for every fixed nonbinary field $\mathbb{F}_q$ with $q\ge 3$ not covered by the large-field algorithms (for example, $\mathbb{F}_3$) — a regime that currently lies between the proved NP-completeness over $\mathbb{F}_2$ and the proved polynomial-time solvability over sufficiently large fields; and give, if one exists, a structural (for example, forbidden-configuration) characterization of the digraphs of min-rank two over every such fixed field $\mathbb{F}_q$.

References

1. Son Hoang Dau, Vitaly Skachek, Yeow Meng Chee. Optimal Index Codes With Near-Extreme Rates. IEEE Transactions on Information Theory 60(3), 2014. DOI: 10.1109/TIT.2013.2295331. https://doi.org/10.1109/TIT.2013.2295331 (extended preprint arXiv:1202.1150, https://arxiv.org/abs/1202.1150; conference version in Proc. IEEE ISIT 2012, DOI: 10.1109/isit.2012.6283852)
2. R. 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. Z. Bar-Yossef, Y. Birk, T. S. Jayram, T. Kol. Index Coding With Side Information. IEEE Transactions on Information Theory 57(3), 2011. DOI: 10.1109/TIT.2010.2103753. https://doi.org/10.1109/TIT.2010.2103753
4. A. Blasiak, R. Kleinberg, E. Lubetzky. Index coding via linear programming. Preprint arXiv:1004.1379, 2010. https://arxiv.org/abs/1004.1379 (journal companion: 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)
5. Hamed Maleki, Viveck R. Cadambe, Syed A. Jafar. Index Coding—An Interference Alignment Perspective. IEEE Transactions on Information Theory 60(9), 2014. DOI: 10.1109/TIT.2014.2338865. https://doi.org/10.1109/TIT.2014.2338865 (preprint arXiv:1205.1483, https://arxiv.org/abs/1205.1483)
6. Lawrence Ong. A new class of index coding instances where linear coding is optimal. 2014 International Symposium on Network Coding (NetCod), 2014. DOI: 10.1109/netcod.2014.6892122. https://doi.org/10.1109/netcod.2014.6892122 (preprint arXiv:1309.4166, https://arxiv.org/abs/1309.4166)
7. Eimear Byrne, Marco Calderini. Bounding the Optimal Rate of the ICSI and ICCSI problem. SIAM Journal on Discrete Mathematics, 2017. DOI: 10.1137/16M107164X. https://doi.org/10.1137/16M107164X (preprint arXiv:1604.05991, https://arxiv.org/abs/1604.05991)
8. Lawrence Ong. Optimal Finite-Length and Asymptotic Index Codes for Five or Fewer Receivers. IEEE Transactions on Information Theory 63(11), 2017. DOI: 10.1109/TIT.2017.2748562. https://doi.org/10.1109/TIT.2017.2748562
9. Dror Chawin, Ishay Haviv. Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank. SIAM Journal on Discrete Mathematics 37(4), 2023. DOI: 10.1137/23m155760x. https://doi.org/10.1137/23m155760x (preprint arXiv:2301.00732, https://arxiv.org/abs/2301.00732)
10. Ishay Haviv. Kernels for storage capacity and dual index coding. Journal of Combinatorial Theory, Series A, 2025. DOI: 10.1016/j.jcta.2025.106059. https://doi.org/10.1016/j.jcta.2025.106059 (preprint arXiv:2504.12274, https://arxiv.org/abs/2504.12274)