  For any undirected graph $G=(V,E)$ and a set $E_W$ of candidate edges with
$E\cap E_W=\emptyset$, the $(k,\gamma)$-spectral augmentability problem is to
find a set $F$ of $k$ edges from $E_W$ with appropriate weighting, such that
the algebraic connectivity of the resulting graph $H=(V,E\cup F)$ is least
$\gamma$. Because of a tight connection between the algebraic connectivity and
many other graph parameters, including the graph's conductance and the mixing
time of random walks in a graph, maximising the resulting graph's algebraic
connectivity by adding a small number of edges has been studied over the past
15 years.
  In this work we present an approximate and efficient algorithm for the
$(k,\gamma)$-spectral augmentability problem, and our algorithm runs in
almost-linear time under a wide regime of parameters. Our main algorithm is
based on the following two novel techniques developed in the paper, which might
have applications beyond the $(k,\gamma)$-spectral augmentability problem.
  (1) We present a fast algorithm for solving a feasibility version of an SDP
for the algebraic connectivity maximisation problem from [GB06]. Our algorithm
is based on the classic primal-dual framework for solving SDP, which in turn
uses the multiplicative weight update algorithm. We present a novel approach of
unifying SDP constraints of different matrix and vector variables and give a
good separation oracle accordingly.
  (2) We present an efficient algorithm for the subgraph sparsification
problem, and for a wide range of parameters our algorithm runs in almost-linear
time, in contrast to the previously best known algorithm running in at least
$\Omega(n^2mk)$ time [KMST10]. Our analysis shows how the randomised BSS
framework can be generalised in the setting of subgraph sparsification, and how
the potential functions can be applied to approximately keep track of different
subspaces.
