Exploiting symmetry in computing polyhedral bounds on network coding rate regions
Jayant Apte, John MacLaren Walsh · 2015
We propose an algorithm for computing polyhedral bounds on the rate regions of multi-source multi-sink network coding instances given the knowledge of symmetries of the instance as captured by the network symmetry group. We show how the network symmetry group can be interpreted as a group of symmetries of a polyhedron, which in turn enables the use techniques for exploiting symmetry in polyhedral computation to reduce the complexity of calculating the rate region. We apply these techniques to the polyhedral projection algorithm chm to list only those facets and extreme points of a polyhedral bound on rate region that are inequivalent under the action of the network symmetry group. Additionally, a generalization of this algorithm that can exploit richer super-groups of polyhedral symmetries, the restricted affine symmetry groups, is discussed.