On the Sparsity of a Linear Network Code for Broadcast Systems with Feedback
One method for reducing the decoding complexity of network coding in wireless broadcast systems is to generate sparse encoding vectors. The problem of finding the minimal Hamming weight of innovative encoding vectors over large finite field is formulated. By reducing the problem of hitting set to it, the authors show that the problem is NP-hard. However when the number of users is fixed, the problem can then be solved in polynomial time. A systematic method for solving the problem is provided.