Linear index coding via graph homomorphism

In [1], [2] it is shown that the minimum broadcast rate of a linear index code over a finite field F_q is equal to an algebraic invariant of the underlying digraph, called minrank_q. In [3], it is proved that for F₂ and any positive integer k, minrank_q(G) ≤ k if and only if there exists a homomorphism from the complement of the graph G to the complement of a particular undirected graph family called “graph family {G_k}”. As observed in [2], by combining these two results one can relate the linear index coding problem of undirected graphs to the graph homomorphism problem. In [4], a direct connection between linear index coding problem and graph homomorphism problem is introduced. In contrast to the former approach, the direct connection holds for digraphs as well and applies to any field size. More precisely, in [4], a graph family {H_k^q} has been introduced and shown that whether or not the scalar linear index of a digraph G is less than or equal to k is equivalent to the existence of a graph homomorphism from the complement of G to the complement of H_k^q. In this paper, we first study the structure of the digraphs H_k^q defined in [4]. Analogous to the result of [2] about undirected graphs, we prove that H_k^q are vertex transitive digraphs. Using this, and by applying a lemma of Hell and Nesetril [5], we derive a class of necessary conditions for digraphs G to satisfy lind_q(G) ≤ k. Particularly, we obtain new lower bounds on lind_q(G). Our next result is about the computational complexity of scalar linear index of a digraph. It is known that deciding whether the scalar linear index of an undirected graph is equal to k or not is NP-complete for k ≥ 3 and is polynomially decidable for k = 1, 2 [3]. For digraphs, it is shown in [6] that for the binary alphabet, the decision- problem for k = 2 is NP-complete. We use graph homomorphism framework to extend this result to arbitrary alphabet.