  We study the problem of maximizing the number of spanning trees in a
connected graph by adding at most $k$ edges from a given candidate edge set. We
give both algorithmic and hardness results for this problem:
  - We give a greedy algorithm that, using submodularity, obtains an
approximation ratio of $(1 - 1/e - \epsilon)$ in the exponent of the number of
spanning trees for any $\epsilon > 0$ in time $\tilde{O}(m \epsilon^{-1} + (n +
q) \epsilon^{-3})$, where $m$ and $q$ is the number of edges in the original
graph and the candidate edge set, respectively. Our running time is optimal
with respect to the input size up to logarithmic factors, and substantially
improves upon the $O(n^3)$ running time of the previous proposed greedy
algorithm with approximation ratio $(1 - 1/e)$ in the exponent. Notably, the
independence of our running time of $k$ is novel, comparing to conventional
top-$k$ selections on graphs that usually run in $\Omega(mk)$ time. A key
ingredient of our greedy algorithm is a routine for maintaining effective
resistances under edge additions in an online-offline hybrid setting.
  - 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)$. This
inapproximability result follows from a reduction from the minimum path cover
in undirected graphs, whose hardness again follows from the constant
inapproximability of the Traveling Salesman Problem (TSP) with distances 1 and
2. Thus, the approximation ratio of our algorithm is also optimal up to a
constant factor in the exponent. To our knowledge, this is the first hardness
of approximation result for maximizing the number of spanning trees in a graph,
or equivalently, by Kirchhoff's matrix-tree theorem, maximizing the determinant
of an SDDM matrix.
