Revisiting the linear information flow algorithm (Q477998)

Let \(G=(V,E)\) be a directed graph with a finite set \(S\) of \(m\) sources and a finite set \(R\) of \(n\) receivers (sinks). The graph \(G\) is acyclic graph and the edges have unit capacity. Therefore \(G\) is an acyclic directed network. The task is to send the information from the all sources to all sinks. The sources will transmit \(m\) linearly independent vectors from a vector space over \(F_q\). The question that this paper addresses is how large does the alphabet \(F_q\) need to be to design a linear network code for a given choice of coding points, a given number of sources and receivers and a fixed but arbitrary initial input from the sources. \textit{P. Sanders} et al. [``Polynomial time algorithms for network information flow'', SPAA 2003: Proc. 15th ACM-IEEE Int. Symp. on Parallel Algorithms and Architectures, San Diego, USA, 286--294 (2003)] have presented the Linear Information Flow (LIF) algorithm for the solution of this problem. \textit{S. Jaggi} [``Low complexity algebraic multicast network codes'', ISIT 2003: Proc. IEEE Int. Symp. on Information Theory, Yokohama, Japan, 368 (2003)] have independently and concurrently developed an algorithm similar to LIF algorithm of Sander et al. In this paper the LIF algorithm is considered in detail and reprise a known proof of it which stresses the underlying geometry. This proof shows that for it to design an arbitrary linear network code it is sufficient to have \(q\geq n\). The author gives an example of a network graph with \( n-1\) coding points, \( n\) sources and \(n\) receivers, which needs \( q=n\). Finally the author demonstrated that this network only requires a binary alphabet to design a linear network code and have explained why the LIF algorithm gives such a poor answer in this case.