A Unification of Menger's and Edmonds' Theorems and Network Coding Theorems

Опубликовано 6 сентября 2016, 5:04

The {\em multicast capacity} is the maximum rate that a sender can communicate common information to a set of receivers in a network. A fundamental theorem in graph theory by Menger determines the unicast capacity from a sender to a receiver; another fundamental theorem in graph theory by Edmonds determines the broadcast capacity from a sender to all other nodes. In both extreme cases, the multicast capacity can be achieved by routing, i.e., replicating or forwarding, information. Recent works on network information flow establish that the multicast capacity is equal to the minimum capacity of cuts separating the sender from a receiver, which can be achieved by performing network coding, while in general it cannot be achieved by routing.   We present a statement that unifies Menger's Theorem, Edmonds' Theorem, and network information flow theorems. Specifically, we show that the multicast capacity can be achieved by linear time-invariant network coding on {\em Steiner edges} (edges pointing into Steiner nodes) only. Our proof is constructive: a polynomial-time algorithm is presented that ``hardwires'' each non-Steiner edge with one of its predecessors while preserving the required connectivity from the sender to each receiver.   This is a joint work with Dr. Kamal Jain and Prof. Sun-Yuan Kung.