A Graph Minor Perspective to Multicast Network Coding

DOI10.1109/TIT.2014.2336836zbMATH Open1360.94226arXiv1305.4905MaRDI QIDQ2986153FDOQ2986153

Yan Wang, Xunrui Yin, Zongpeng Li, Xiangyang Xue, Xin Wang

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Network Coding encourages information coding across a communication network. While the necessity, benefit and complexity of network coding are sensitive to the underlying graph structure of a network, existing theory on network coding often treats the network topology as a black box, focusing on algebraic or information theoretic aspects of the problem. This work aims at an in-depth examination of the relation between algebraic coding and network topologies. We mathematically establish a series of results along the direction of: if network coding is necessary/beneficial, or if a particular finite field is required for coding, then the network must have a corresponding hidden structure embedded in its underlying topology, and such embedding is computationally efficient to verify. Specifically, we first formulate a meta-conjecture, the NC-Minor Conjecture, that articulates such a connection between graph theory and network coding, in the language of graph minors. We next prove that the NC-Minor Conjecture is almost equivalent to the Hadwiger Conjecture, which connects graph minors with graph coloring. Such equivalence implies the existence of $K_4$, $K_5$, $K_6$, and $K_{O(q/logq)}$ minors, for networks requiring $mathbb{F}_3$, $mathbb{F}_4$, $mathbb{F}_5$ and $mathbb{F}_q$, respectively. We finally prove that network coding can make a difference from routing only if the network contains a $K_4$ minor, and this minor containment result is tight. Practical implications of the above results are discussed.

Full work available at URL: https://arxiv.org/abs/1305.4905

Mathematics Subject Classification ID

Source coding (94A29)

This page was built for publication: A Graph Minor Perspective to Multicast Network Coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986153)