Active information fusion is to selectively choose the sensors so that the information gain can compensate the cost spent in information gathering. However, determining the most informative and cost-effective sensors requires an evaluation of all possible sensor combinations, which is computationally intractable, particularly, when information-theoretic criterion is used. This paper presents a methodology to actively select a sensor subset with the best tradeoff between information gain and sensor cost by exploiting the synergy among sensors. Our approach includes two aspects: a method for efficient mutual information computation and a graph-theoretic approach to reduce search space. The approach can reduce the time complexity significantly in searching for a near optimal sensor subset.