Network coding: A computational perspective

In this work, we study the computational perspective of network coding, focusing on two issues. First, we address the computational complexity of finding a network code for acyclic multicast networks. Second, we address the issue of reducing the amount of computation performed by the network nodes. In particular, we consider the problem of finding a network code with the minimum possible number of encoding nodes, i.e., nodes that generate new packets by combining the packets received over incoming links. We present a deterministic algorithm that finds a feasible network code for a multicast network over an underlying graph G(V, E) in time O(|E|kh + |V|k²h² + h⁴k³(k + h)), where k is the number of destinations and h is the number of packets. This improves the best known running time of O(|E|kh + |V|k²h²(k + h)) of Jaggi et al. [1] in the typical case of large communication graphs. In addition, our algorithm guarantees that the number of encoding nodes in the obtained network code is bounded by O(h ³k²). Next, we address the problem of finding a network code with the minimum number of encoding nodes in both integer and fractional coding networks. We prove that in the majority of settings this problem is NP-hard. However, we show that if h = O(1) and k = O(1) and the underlying communication graph is acyclic, then there exists an algorithm that solves this problem in polynomial time.