We consider the problem of minimizing the number of network coding nodes in a multicast scenario, with the purpose of minimizing the overall encoding cost. We give a heuristic polynomial-time algorithm to approximate the minimum number of network coding nodes required to reach a given flow rate and show that it performs well in practice when the number of receivers is small. We also find that many topologies do not require any network coding nodes to reach the maximum achievable throughput.