Searching for Capacity Factors is NP-Complete
Y. Li, Zheng Huang, Xingyu Wang, Haibin Kan · 2008
In this paper we investigate the problems of searching for the capacity factors and determining the capacity ranks of edges in a network coding-based network, which were first proposed in (K. Cai and P.Y. Fan, 2007). For the former problem, we prove that it is computationally hard by reducing the well known NP-complete SUB-SUM problem to the current problem. For the latter problem, we devise efficient algorithms in a special case of networks and conjecture that in general case the problem is also hard.