Various network monitoring and performance evaluation schemes generate considerable amount of traffic, which affects network performance. In this paper we describe a method for minimizing network monitoring overhead based on shortest path tree (SPT) protocol. We describe two different variations of the problem: the A-problem and the E-problem, and show that there is a significant difference between them. We prove that finding optimal solutions is NP-hard for both variations, and propose a theoretically best possible heuristic for the A-problem and three different heuristics for the E-problem, one of them being also theoretically best possible. We show that one can compute in polynomial time an O(ln|V|)-approximate solution for each of these problems. Then, we analyze the performance of our heuristics on large graphs generated using Waxman and power-law models as well as on real ISP topology maps. Experiment results show more than 80% improvement when using our heuristics on real topologies over the naive approaches