  The minimum spanning tree of a graph is a well-studied structure that is the
basis of countless graph theoretic and optimization problem. We study the
minimum spanning tree (MST) perturbation problem where the goal is to spend a
fixed budget to increase the weight of edges in order to increase the weight of
the MST as much as possible. Two popular models of perturbation are bulk and
continuous. In the bulk model, the weight of any edge can be increased exactly
once to some predetermined weight. In the continuous model, one can pay a
fractional amount of cost to increase the weight of any edge by a proportional
amount. Frederickson and Solis-Oba \cite{FS96} have studied these two models
and showed that bulk perturbation for MST is as hard as the $k$-cut problem
while the continuous perturbation model is solvable in poly-time. In this
paper, we study an intermediate unit perturbation variation of this problem
where the weight of each edge can be increased many times but at an integral
unit amount every time. We provide an $(opt/2 -1)$-approximation in polynomial
time where $opt$ is the optimal increase in the weight. We also study the
associated dual targeted version of the problem where the goal is to increase
the weight of the MST by a target amount while minimizing the cost of
perturbation. We provide a $2$-approximation for this variation. Furthermore we
show that assuming the Small Set Expansion Hypothesis, both problems are hard
to approximate. We also point out an error in the proof provided by
Frederickson and Solis-Oba in \cite{FS96} with regard to their solution to the
continuous perturbation model. Although their algorithm is correct, their
analysis is flawed. We provide a correct proof here.
