Article Contents
Article Contents

Network encoding complexity: Exact values, bounds, and inequalities

Results of this paper have been partially presented in the 49th Allerton Conference on Communication, Control and Computing [15], and the 2012 International Symposium on Information Theory and its Applications [14]

The last author would like to thank the support from the University Grants Committee of the Hong Kong Special Administrative Region, China under grant No. AoE/E-02/08 and the support from Research Grants Council of the Hong Kong Special Administrative Region, China under grant No. 17301814.
• For an acyclic directed network with multiple pairs of sources and sinks and a set of Menger's paths connecting each pair of source and sink, it is known that the number of mergings among these Menger's paths is closely related to network encoding complexity. In this paper, we focus on networks with two pairs of sources and sinks and we derive bounds on and exact values of two functions relevant to encoding complexity for such networks.

Mathematics Subject Classification: Primary: 94A29; Secondary: 05C40.

 Citation:

• Figure 1.  Paths $\beta_1, \beta_2$ merge at edge $A \to B$ and at merged subpath (or merging) $A \to B \to C \to D$, and paths $\beta_1, \beta_2, \beta_3$ merge at edge $B \to C$ and at merged subpath (or merging) $B\to C$ (Here, arrows in the figure represents edges, and the terminal points of arrows should be naturally interpreted as vertices; the same convention applies to other figures in this paper)

Figure 2.  (a) Network coding in the butterfly network (b) Network coding in a two-way channel (c) Network coding in two sessions of unicast

Figure 3.  An example of a reroutable graph

Figure 4.  Two examples of merging sequences (as in Remark 3.3, all the mergings in this figure are represented by solid dots instead)

Figure 5.  Two examples of alternating sequences

Figure 6.  (a) A non-reroutable (2, 3)-graph with 8 mergings (b) An example of a (2, 5)-graph

Figure 7.  Graph $\mathcal{E}(4, 4)$ with $9$ mergings

Figure 8.  (a) Graph $\mathcal{F}(3, 3)$ with $11$ mergings (b) Splitting of $R_1$ in $\mathcal{F}(3, 3)$

Figure 9.  Concatenation of $\mathcal{F}(2, 2)$ and a non-reroutable $(2, 2)$-graph

Figure 10.  Partition a $(3, c_2)$-graph into blocks

Figure 11.  Case 1

Figure 12.  Case 2

Figure 13.  Concatenation of two (3, 3)-graphs

Figure 14.  Concatenation of a (2, 2)-graph and a (4, 4)-graph

•  [1] M. Bicknell, A primer on the Pell sequence and related sequences, Fibonacci Quart., 13 (1975), 345-349. [2] K. Cai, K. B. Letaief, P. Fan and R. Feng, On the solvability of 2-pair networks – a cut-based characterization, Phys. Commun., 6 (2013), 124-133. [3] T. M. Cover and J. A. Thomas, Elements of Information Theory 2nd edition, Wiley-Interscience, New York, 2006. [4] J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19 (1972), 248-264. [5] R. Graham, B. Rothschild and J. Spencer, Ramsey Theory 2nd edition, John Wiley Sons, New York, 1990. [6] G. Han, Menger's paths with minimum mergings, in Proc. 2009 IEEE Inf. Theory Workshop Netw. Inf. Theory, 2009. 271–275. [7] S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain and L. Tolhuizen, Polynomial time algorithms for multicast network code construction, IEEE Trans. Inf. Theory, 51 (2005), 1973-1982.  doi: 10.1109/TIT.2005.847712. [8] M. Langberg, A. Sprintson and J. Bruck, The encoding complexity of network coding, IEEE Trans. Inf. Theory, 52 (2006), 2386-2397.  doi: 10.1109/TIT.2006.874434. [9] S.-Y. R. Li, R. W. Yeung and N. Cai, Linear network coding, IEEE Trans. Inf. Theory, 49 (2003), 371-381.  doi: 10.1109/TIT.2002.807285. [10] K. Menger, Zur allgemeinen Kurventheorie, Fundam. Math., 10 (1927), 96-115. [11] W. Song, K. Cai, R. Feng and R. Wang, The complexity of network coding with two unit-rate multicast sessions, IEEE Trans. Inf. Theory, 59 (2003), 5692-5707.  doi: 10.1109/TIT.2013.2262492. [12] W. Song, K. Cai, C. Yuen and R. Feng, On the solvability of 3s/nt sum-network – a region decomposition and weak decentralized code method, preprint, arXiv: 1502.00762 [13] A. Tavory, M. Feder and D. Ron, Bounds on linear codes for network multicast, Electr. Colloq. Comput. Complexity, 10 (2003), 1-28. [14] E. L. Xu, W. Shang and G. Han, A graph theoretical approach to network encoding complexity, in Proc. 2012 Int. Symp. Inf. Theory Appl. , 2012,396–400. doi: 10.1007/978-1-4614-1800-9_176. [15] L. Xu and G. Han, Bounds and exact values in network encoding complexity with two sinks, in Proc. 49th Ann. Allerton Conf. Commun. Control Comput. , 2011,1462–1469. [16] R. W. Yeung, Information Theory and Network Coding Springer-Verlag, New York, 2008. [17] R. W. Yeung, S. -Y. R. Li, N. Cai and Z. Zhang, Network Coding Theory Now Publishers, Delft, Netherlands, 2006.

Figures(14)