Maximizing the Number of Spanning Trees in a Connected Graph

We study the problem of maximizing the number of spanning trees in a connected graph with n vertices and m edges, by adding at most k edges from a given set of q candidate edges, a problem that has applications in many domains. We give both algorithmic and hardness results for this problem: 1) We give a greedy algorithm that obtains an approximation ratio of (1 - 1/e - ∈) in the exponent of the number of spanning trees for any ∈ > 0 in time Õ(m∈ -1 + (n + q)∈ -3 ), where Õ(·) hides poly log(n) factors. Our running time is optimal with respect to the input size, up to logarithmic factors, and improves on the O(n 3 ) running time of the previous proposed greedy algorithm with an approximation ratio (1 - 1/e) in the exponent. Notably, the independence of our running time of k is novel, compared to conventional top-k selections on graphs that usually run in Ω(mk) time. 2) We show the exponential inapproximability of this problem by proving that there exists a constant c > 0 such that it is NP-hard to approximate the optimum number of spanning trees in the exponent within (1 - c).