# American Institute of Mathematical Sciences

August  2017, 11(3): 567-594. doi: 10.3934/amc.2017044

## Network encoding complexity: Exact values, bounds, and inequalities

 1 Department of Electrical and Computer Engineering, Texas A & M University, College Station, TX 77843, USA 2 Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450001, China 3 Department of Mathematics, University of Hong Kong, Pokfulam Road, Hong Kong, China

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]

Received  November 2015 Revised  September 2016 Published  August 2017

Fund Project: 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.

Citation: Easton Li Xu, Weiping Shang, Guangyue Han. Network encoding complexity: Exact values, bounds, and inequalities. Advances in Mathematics of Communications, 2017, 11 (3) : 567-594. doi: 10.3934/amc.2017044
##### References:
 [1] M. Bicknell, A primer on the Pell sequence and related sequences, Fibonacci Quart., 13 (1975), 345-349. Google Scholar [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. Google Scholar [3] T. M. Cover and J. A. Thomas, Elements of Information Theory 2nd edition, Wiley-Interscience, New York, 2006. Google Scholar [4] J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19 (1972), 248-264. Google Scholar [5] R. Graham, B. Rothschild and J. Spencer, Ramsey Theory 2nd edition, John Wiley Sons, New York, 1990. Google Scholar [6] G. Han, Menger's paths with minimum mergings, in Proc. 2009 IEEE Inf. Theory Workshop Netw. Inf. Theory, 2009. 271–275.Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [10] K. Menger, Zur allgemeinen Kurventheorie, Fundam. Math., 10 (1927), 96-115. Google Scholar [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. Google Scholar [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.00762Google Scholar [13] A. Tavory, M. Feder and D. Ron, Bounds on linear codes for network multicast, Electr. Colloq. Comput. Complexity, 10 (2003), 1-28. Google Scholar [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. Google Scholar [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.Google Scholar [16] R. W. Yeung, Information Theory and Network Coding Springer-Verlag, New York, 2008.Google Scholar [17] R. W. Yeung, S. -Y. R. Li, N. Cai and Z. Zhang, Network Coding Theory Now Publishers, Delft, Netherlands, 2006.Google Scholar

show all references

##### References:
 [1] M. Bicknell, A primer on the Pell sequence and related sequences, Fibonacci Quart., 13 (1975), 345-349. Google Scholar [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. Google Scholar [3] T. M. Cover and J. A. Thomas, Elements of Information Theory 2nd edition, Wiley-Interscience, New York, 2006. Google Scholar [4] J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19 (1972), 248-264. Google Scholar [5] R. Graham, B. Rothschild and J. Spencer, Ramsey Theory 2nd edition, John Wiley Sons, New York, 1990. Google Scholar [6] G. Han, Menger's paths with minimum mergings, in Proc. 2009 IEEE Inf. Theory Workshop Netw. Inf. Theory, 2009. 271–275.Google Scholar [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. Google Scholar [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. Google Scholar [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. Google Scholar [10] K. Menger, Zur allgemeinen Kurventheorie, Fundam. Math., 10 (1927), 96-115. Google Scholar [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. Google Scholar [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.00762Google Scholar [13] A. Tavory, M. Feder and D. Ron, Bounds on linear codes for network multicast, Electr. Colloq. Comput. Complexity, 10 (2003), 1-28. Google Scholar [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. Google Scholar [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.Google Scholar [16] R. W. Yeung, Information Theory and Network Coding Springer-Verlag, New York, 2008.Google Scholar [17] R. W. Yeung, S. -Y. R. Li, N. Cai and Z. Zhang, Network Coding Theory Now Publishers, Delft, Netherlands, 2006.Google Scholar
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)
(a) Network coding in the butterfly network (b) Network coding in a two-way channel (c) Network coding in two sessions of unicast
An example of a reroutable graph
Two examples of merging sequences (as in Remark 3.3, all the mergings in this figure are represented by solid dots instead)
Two examples of alternating sequences
(a) A non-reroutable (2, 3)-graph with 8 mergings (b) An example of a (2, 5)-graph
Graph $\mathcal{E}(4, 4)$ with $9$ mergings
(a) Graph $\mathcal{F}(3, 3)$ with $11$ mergings (b) Splitting of $R_1$ in $\mathcal{F}(3, 3)$
Concatenation of $\mathcal{F}(2, 2)$ and a non-reroutable $(2, 2)$-graph
Partition a $(3, c_2)$-graph into blocks
Case 1
Case 2
Concatenation of two (3, 3)-graphs
Concatenation of a (2, 2)-graph and a (4, 4)-graph
 [1] Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577 [2] Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145 [3] Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95 [4] Kashi Behrstock, Michel Benaïm, Morris W. Hirsch. Smale strategies for network prisoner's dilemma games. Journal of Dynamics & Games, 2015, 2 (2) : 141-155. doi: 10.3934/jdg.2015.2.141 [5] F. Ali Mehmeti, R. Haller-Dintelmann, V. Régnier. Dispersive waves with multiple tunnel effect on a star-shaped network. Discrete & Continuous Dynamical Systems - S, 2013, 6 (3) : 783-791. doi: 10.3934/dcdss.2013.6.783 [6] Michelle L.F. Cheong, Rohit Bhatnagar, Stephen C. Graves. Logistics network design with supplier consolidation hubs and multiple shipment options. Journal of Industrial & Management Optimization, 2007, 3 (1) : 51-69. doi: 10.3934/jimo.2007.3.51 [7] Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial & Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251 [8] Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics & Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016 [9] Joanna Tyrcha, John Hertz. Network inference with hidden units. Mathematical Biosciences & Engineering, 2014, 11 (1) : 149-165. doi: 10.3934/mbe.2014.11.149 [10] T. S. Evans, A. D. K. Plato. Network rewiring models. Networks & Heterogeneous Media, 2008, 3 (2) : 221-238. doi: 10.3934/nhm.2008.3.221 [11] David J. Aldous. A stochastic complex network model. Electronic Research Announcements, 2003, 9: 152-161. [12] Pradeep Dubey, Rahul Garg, Bernard De Meyer. Competing for customers in a social network. Journal of Dynamics & Games, 2014, 1 (3) : 377-409. doi: 10.3934/jdg.2014.1.377 [13] Suzana Antunović, Tonči Kokan, Tanja Vojković, Damir Vukičević. Exponential generalised network descriptors. Advances in Mathematics of Communications, 2019, 13 (3) : 405-420. doi: 10.3934/amc.2019026 [14] Jianfeng Feng, Mariya Shcherbina, Brunello Tirozzi. Stability of the dynamics of an asymmetric neural network. Communications on Pure & Applied Analysis, 2009, 8 (2) : 655-671. doi: 10.3934/cpaa.2009.8.655 [15] Zari Dzalilov, Iradj Ouveysi, Alexander Rubinov. An extended lifetime measure for telecommunication network. Journal of Industrial & Management Optimization, 2008, 4 (2) : 329-337. doi: 10.3934/jimo.2008.4.329 [16] Shruti Agarwal, Gilles Carbou, Stéphane Labbé, Christophe Prieur. Control of a network of magnetic ellipsoidal samples. Mathematical Control & Related Fields, 2011, 1 (2) : 129-147. doi: 10.3934/mcrf.2011.1.129 [17] Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225 [18] Dirk Helbing, Jan Siegmeier, Stefan Lämmer. Self-organized network flows. Networks & Heterogeneous Media, 2007, 2 (2) : 193-210. doi: 10.3934/nhm.2007.2.193 [19] R.L. Sheu, M.J. Ting, I.L. Wang. Maximum flow problem in the distribution network. Journal of Industrial & Management Optimization, 2006, 2 (3) : 237-254. doi: 10.3934/jimo.2006.2.237 [20] Delio Mugnolo. Gaussian estimates for a heat equation on a network. Networks & Heterogeneous Media, 2007, 2 (1) : 55-79. doi: 10.3934/nhm.2007.2.55

2018 Impact Factor: 0.879