11institutetext: Paris Dauphine University
11email<EMAIL_ADDRESS>22institutetext: Ecole Normale Superieure
22email<EMAIL_ADDRESS>33institutetext: Biocomplexity Institute and
Initiatives at University of Virginia
33email<EMAIL_ADDRESS>
44institutetext: Tepper School of Business, Carnegie Mellon University
44email<EMAIL_ADDRESS>

# Unit Perturbations in Budgeted Spanning Tree Problems

Hassene Aissi 11 Solal Attias 22 Da Qi Chen 33 R. Ravi This material is based
upon work supported in part by the U. S. Office of Naval Research under award
number N00014-18-1-2099 and the Air Force Office of Scientific Research under
award number FA9550-20-1-008044

###### Abstract

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 [12] 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 [12] 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.

##  1 Introduction

Classic problems in network optimization involve minimizing (or maximizing)
the cost of interesting combinatorial objects such as cuts, paths or trees.
The motivation for Ford and Fulkerson’s study of the minimum $st$-cut problem
[21, 36, 8] was to examine how much an enemy can interdict the network with a
limited budget and hence reduce the capacity of the minimum cut to the lowest
possible value under different costs for capacity reduction at the arcs. The
minimum $st$-cut problem is posed in a directed graph with non-negative arc
capacities and special source $s$ and sink $t$ with the goal of finding the
minimum capacity of a cut separating all paths from $s$ to $t$. In early work,
Fulkerson [16] also introduced a budgeted version of this minimum $st$-cut
problem. Here in addition to the capacities, each arc is also provided with a
cost to increase its capacity by one unit and a global budget $B>0$ on the
total cost that can be spent with the goal of maximizing the minimum cut after
carrying out the increases within budget. Ahuja and Orlin [1] later showed how
this algorithm can be made to run in strongly polynomial time.

Fulkerson and Harding [15] studied the analogue of this problem for the case
of minimum-length $st$-paths. In the shortest $st$-path problem in a directed
graph with non-negative arc lengths and special source $s$ and destination
$t$, the goal is to find the minimum length path from $s$ to $t$. The budgeted
version addressed in [15] specifies an integral cost per unit increase of the
length for each arc and a budget $b$ and seeks to maximize the shortest
$st$-path under this constraint. They reduce this problem to an instance of
parametric minimum-cost flow which is also known to be solvable in polynomial
time [38].

The study of budgeted problems for the case of minimum weight spanning trees
in undirected graphs was initiated by Frederickson and Solis-Oba [14]. The
minimum spanning tree problem in a given undirected graph with non-negative
edge weights is to find a spanning tree of minimum total edge weight. The
budgeted version specifies costs per unit increase in the weight of the edges
and a budget $B>0$ and requires spending the budget optimally to increase the
edge-weights to maximize the weight of the resulting minimum-weight spanning
tree. Frederickson and Solis-Oba gave a strongly polynomial algorithm for this
problem. In follow-up work [13], they extended this solution to that of
maximizing the minimum weight base of matroids for which independence can be
tested in polynomial time.

Juttner [24] extended the study of strongly polynomial time algorithms for
such budgeted optimization problems to a larger class extending the work of
[13] to the budgeted cases of minimum-cost circulations, matroid intersections
and submodular optimization.

###  1.1 Budgeted versus Target Versions

In contrast to requiring that the total cost-spent is no more than a pre-
specified budget $B$ so as to maximize the minimum-weight solution, an
alternate formulation is to specify a target final value $T$ for the minimum
weight solution and minimize the total cost spent in increasing the weights of
the edges to achieve this target. Note that a polynomial time algorithm for
one version usually yields a polynomial time algorithm for the other, by
carrying out a binary search over the specified parameter and optimizing the
other; however, this strategy does not directly yield strongly polynomial
algorithms. We will study both the original budgeted and the dual targeted
versions of the problem in this paper.

###  1.2 Discrete Perturbation Models

We remark that all the above budgeted optimization formulations allow
fractional changes, i.e., if we increase the weight of an edge $e$ by any
$\delta>0$, we pay $\delta\cdot c(e)$ where $c(e)$ is the cost per unit weight
increase for the edge $e$. We may think of this as the continuous version of
these problems. A natural direction to investigate is the discrete version of
these problems where the changes to the elements (edges) are only allowed to
be discrete units.

Frederickson and Solis-Oba [14] introduce an even simpler version of the
discrete version of the robust minimum spanning tree problem: for a given
value $k$, find the set of $k$ edges whose removal from the graph causes the
largest increase in the weight of its minimum spanning trees. They point out
that this problem already appears in the literature under the name of the most
vital edges in the MST [19, 20, 23, 28, 39]. The most vital arcs problem has
also been studied in the context of shortest $st$-paths [3, 32].

###  1.3 Bulk versus Unit Perturbations

We distinguish between two types of discrete perturbation models: bulk and
unit. In the bulk perturbation models, each edge is specified with a bulk
reduction in its weight for which a modification cost must be paid in full for
any modification to be effected at all. More generally, each edge has a series
of integer-valued successive modifications in its weight that can be effected
by a corresponding set of modification costs, each of which must be paid in
full to effect these modifications. In contrast, the unit perturbation model
specifies for each edge, a unit modification cost, and bounds (upper or lower,
depending on whether the modification is an increase or decrease of weight
respectively) and modifications can be made one unit at a time until the
bound. In both models, in the budgeted version, we are given a budget $B$ on
the total modification budget and the objective as before is to increase the
cost of a minimum cost solution. Similarly, for the targeted version, we are
given a target $T$ on the final value of the objective and the goal is to
minimize the modification cost so as to reach the target value $T$ in the
objective after these modifications.

As a simple example, consider the targeted unit-perturbation version of the
$st$-minimum cut problem in a digraph with edge capacities. Assume that we
have an estimate of fortification cost $r_{a}$ for every arc to increase its
capacity by one unit; we assume that the fortification costs are valid for any
starting capacity in a given range. Given a target $T$, the goal is to
increase the capacities on a subset of arcs at minimum fortification cost so
that the minimum $st$-cut in the fortified network is at least $T$. We may
have individual limits on how much each arc can be fortified in total. We
insist that the total capacity increase in each arc is integral to retains the
combinatorial flavor in the discrete problem. This model is “smoother” than
the bulk model where every edge has a fixed integral capacity increase
(potentially greater than one) for which the full upgrading cost has to be
paid: any smaller use of the budget does not upgrade the edge at all. In
contrast to the more popular interdiction problems modeling an attacker’s
concerted effort to weaken a network, fortification (such as infrastructure
replenishment) is typically carried out over time. The unit-upgrading is more
natural in this context of incremental upgrading of elements over time.
Indeed, it is known that under the bulk model that requires us to pay a single
cost to increase the capacity by an arbitrarily large amount, the minimum
$st$-cut fortification problem is as hard as the notorious densest subgraph
(DkS) problem (See [8] for a reduction). Henceforth we focus our attention in
the rest of this paper on the unit perturbation models.

###  1.4 Problem Formulations

In this paper, we study both the targeted and budget version of the minimum
weight spanning tree problem under unit perturbations. We use $(G,w)$ to
denote the input graph $G$ with edge weights $w$. Given an upgrading scheme,
let $c_{x}:=c\cdot x=\sum_{e\in E(G)}c_{e}x_{e}$ is the total cost of this
upgrading.

######  Problem 1.

(Budgeted MMST) Given a graph $G$, functions $w,c:E(G)\to\mathbb{N}$ and a
budget $B$, let $f_{x}$ be the weight of an MST in $(G,w+x)$. Then, find an
upgrading scheme $x:E(G)\to\mathbb{N}$ that maximizes $f_{x}-f_{0}$ while
ensuring the total cost, $c_{x}:=c\cdot x$, is at most $B$. We call $f_{G}(B)$
this maximum value.

Note that we have modelled the increase in the weight of the MST as the
target, which is more general/powerful than making the target the final weight
of the MST.

We also consider the targeted version of this problem:

######  Problem 2.

(Targeted MMST) Given a graph $G$, functions $w,c:E(G)\to\mathbb{N}$ and a
target increase of $T-T_{0}$ where $T_{0}$ is the weight of the MST in
$(G,w)$, find a perturbation scheme $x:E(G)\to\mathbb{N}$ that minimizes the
cost $c_{x}:=c\cdot x$ while ensuring that $f_{x}$ the weight of any MST in
$(G,w+x)$, is at least $T$.

We define two related versions of the problems we study.

######  Problem 3.

(Continuous Budgeted MMST) Given a graph $G$, functions
$w,c:E(G)\to\mathbb{N}$ and a budget $B$, let let $f_{x}$ be the weight of an
MST in $(G,w+x)$. . Then, find a upgrading scheme $x:E(G)\to\mathbb{R^{+}}$
that maximizes $f_{x}-f_{0}$ while ensuring the total cost, $c_{x}:=c\cdot x$,
is at most $B$. We call $f_{G}(B)$ this maximum value.

######  Problem 4.

(Continuous Targeted MMST) Given a graph $G$, functions
$w,c:E(G)\to\mathbb{N}$ and a target increase value of $T-T_{0}$ where $T_{0}$
is the weight of the MST in $(G,w)$, find a upgrading scheme
$x:E(G)\to\mathbb{R^{+}}$ that minimizes the cost $c_{x}:=c\cdot x$ while
ensuring that $f_{x}$ the weight of any MST in $(G,w+x)$, is at least $T$.

Frederickson and Solis-Oba study the above continuous version of the Budgeted
MMST problem and provide an optimal polynomial time algorithm [12], where the
key difference is that the upgrading amounts on the edges are allowed to be
fractional rather than integral values.

All of the above problems permit a natural generalization with individual
upper bounds on the fortification or upgrading amounts on the edges.

######  Problem 5.

(MMSTU) Given a graph $G$ and functions $w,c,u:E(G)\to\mathbb{N}$ and a budget
$B$, find an upgrading scheme $x:E(G)\to\mathbb{N}$, with $\forall e\in
E(G),x(e)\leq u(e)$, that maximizes $f_{x}-f_{0}$ while ensuring $c_{x}\leq
B$.

We notice that the algorithm of Frederickson and Solis-Oba [12] is optimal
even with upper bounds, since the proof is not changed with upper bounds.

###  1.5 Contributions

  1. 1.

Frederickson and Solis-Oba [12] prove that for the budgeted version of
Continuous MMST an optimal solution can be found in polynomial time. However,
there is an error in the proof of the optimality of their algorithm. We point
out the mistake and provide a correct proof. (Section 2)

  2. 2.

We provide a 2-approximation for the targeted version of the unit-perturbation
MMST. For the budgeted version, we provide a $\frac{opt}{2}-1$-solution, an
algorithm that gives an upgrading scheme where the increase in the weight of
the MST is at least $\frac{opt}{2}-1$, where $opt$ is the optimal increase in
the weight of the MST. (Section 3)

  3. 3.

We show that both versions of MMST are NP-complete even with unit upgrading
costs. We use reductions from the minimum-weight $k$-cut problem where the
goal is to find a minimum weight set of edges to break the graph into at least
$k$ connected components, and from the complementary Max Components problem of
using a given budget to delete edges (of total weight within this budget) so
as to maximize the number of resulting connected components. By using
appropriate approximation-preserving reductions and the known hardness results
for these two problems, we get the following implications that show that our
approximation algorithms are (nearly) best possible: Assuming the Small Set
Expansion Hypothesis (SSEH) [33], Targeted Discrete MMST is NP-hard to
approximate to a $(2-\varepsilon)$-factor for $\varepsilon>0$. Similarly,
assuming SSEH, Budgeted Discrete MMST is NP-hard to approximate to a
$(\frac{1}{2}+\varepsilon)$-factor for $\varepsilon>0$. (Section 4)

  4. 4.

The complexity of MMST with unit costs for upgrading any edge and the same
starting weights for all edges in the graph is unresolved. Hence we study this
special case of the Targeted MMST on an undirected graph with $n$ nodes where
all edges have the same initial starting weight and MST weight target $T$, and
give an optimal algorithm that runs in $n^{O(T)}$ time. For this, we use a
supermodularity property of a coverage function used in the analysis. For the
analogous budgeted version with budget $B$, this also implies an optimal
algorithm running in time $n^{O(B)}$. (Section 5)

###  1.6 Related Work

Somewhat tangentially related to our work is the attacker’s problem of
interdicting the network to decrease the weight of the minimum weight
structure in the network. Such interdiction problems have a rich and long
history in Combinatorial Optimization including serving as the motivation for
Ford and Fulkerson’s study of the minimum $st$-cut problem [21, 36, 8]. The
goal there is typically to worsen the optimum value for a structure that an
enemy is trying to build by attacking or interdicting edges or nodes of the
graph. Examples of interdicted structures studied include matchings [43],
minimum spanning trees [2, 46], shortest paths [17, 22], $st$-flows [34, 41,
44] and global minimum cuts [45]. [7] contains a good overview of the current
literature.

Related to the problem of increasing the weight of the MST that we study,
prior work [27, 29] has addressed the problem of decreasing the total cost or
bottleneck cost of the MST by paying upgrading costs on the nodes that in turn
reduce the weight of the incident edges.

##  2 Correctness of MST Upgrading

###  2.1 Introduction of the problem

Frederickson and Solis-Oba studied the continuous version of the Budgeted MMST
problem [12], and prove that an optimal solution can be found in polynomial
time. However, there is an error in the proof of the optimality of their
algorithm. We emphasize that their algorithm is correct. In this section, we
point out the mistake and provide a correct proof.

Let us first introduce the vocabulary used in [12]. Given $S\subset E$, let
$c(S)=\sum_{e\in S}c(e)$. We define $coverage(S,G)$ as the minimum number of
edges that any minimum spanning tree (under the current weights $w$) of $G$
shares with $S$. We say that a set $S$ is lifted by $\delta$ when the weight
of every edge in $S$ is increased by the same amount $\delta$. Let
$tolerance(S,G)$ be the maximum amount that the weights of the edges in $S$
can be lifted by until $coverage(S,G)$ changes (It can be shown that the
coverage will only decrease at this change). Define
$inc\\_cost(S,G):=c(S)/coverage(S,G)$, the cost per unit increment of $S$.
Roughly, the algorithm in [12] is greedy and chooses a set $S$ of minimum
$inc\\_cost$ value in the current weighted graph and lifts the weights of all
the edges in it by its $tolerance$ or until it runs out of budget (whichever
occurs first).

Let $\widetilde{G_{w_{i}}}$ be the graph obtained from $G$ by first deleting
all edges of weight strictly larger than $w_{i}$ and then contracting all
edges of weight strictly smaller than $w_{i}$. For an edge $e\in E(G)$, let
$sm\\_eq(e,G)$ be the set of edges in $G$ whose weights are at most the weight
of $e$.

We first point out the following observation. Let $T$ be an MST of $G$ and let
$T_{w_{i}}$ be the set of edges of weight $w_{i}$ in $T$. Then, it is easy to
check that $T_{w_{i}}$ forms a spanning forest in $\widetilde{G_{w_{i}}}$.
Thus, if $S$ is a set of edges in $G$ with the same weight $w_{i}$, then
$coverage(S,G)$ is equal to the increase in the number of components of
$\widetilde{G_{w_{i}}}$ after deleting $S$.

###  2.2 Continuous Downgrading of MSTs

In [12], Frederickson and Solis-Oba proposed the following algorithm to
maximize the weight of the MSTs in the resulting graph. Note that when there
is a choice of sets $S$ that minimize $inc\\_cost$, the algorithm is free to
choose any.

1: $balance\leftarrow B$;

2: $wmst$ $\leftarrow$ weight of a minimum spanning tree of $G$;

3: while $balance>0$ do

4: Find a set $S$ that minimizes $inc\\_cost(S,G)$;

5: $A\leftarrow min\\{tolerance(S,G),balance/c(S)\\}$;

6: Lift the weights of the edges in $S$ by $A$;

7: $balance\leftarrow balance-A*c(S)$;

8: end while

9: $increase\leftarrow$ (weight of a minimum spanning tree of $G$)$-wmst$;

10: Output $increase$;

Algorithm 1 raise_mst $(G,w,c,B)$

Unfortunately, the proof of optimality of the algorithm (Theorem 3.1 in [12])
is incorrect. The main idea of their proof is to first decompose any given
optimal solution into a sequence of fractional lifts (where a lift corresponds
to the action of increasing a set of edges by the same amount). Then, at any
partial budget $b<B$, one can identify $S_{b}^{*}$, the set of arcs being
lifted after spending $b$ budget according to the decomposition of the optimal
solution. Then, one can compare $S_{b}^{*}$ to $S_{b}$, the set of arcs lifted
by $raise\\_mst$ after spending $b$ budget. The error in their proof arises in
their decomposition wherein their definition of $S_{b}^{*}$ is not a lift. We
explain why this is important in the rest of the proof next. As a last step in
their proof, they show that $S_{b}$ performs as well as $S_{b}^{*}$ for any
$b$ by using the following lemma (Lemma 3.1 in [12]).

######  Lemma 1 (Lemma 3.1 in [12]).

Let $G,G^{\prime}$ be two graphs on the same vertex and edge sets but has
edge-weights $w,w^{\prime}$ respectively. Let $S$ be a set of edges such that
for every $e\in S$, $sm\\_eq(e,G^{\prime})\subseteq sm\\_eq(e,G)$. Then, then
$coverage(S,G)\leq coverage(S,G^{\prime})$.

Given the decomposition, let $G_{b}^{*}$ and $G_{b}$ be the state of the graph
after spending budget $b$ according to the decomposition of the optimal
solution and $raise\\_mst$ respectively. Let $w_{b^{*}},w_{b}$ be the weight
function of the edges in $G_{b}^{*}$ and $G_{b}$ respectively. In the
discussion following their proof of Lemma 1, they pointed out that if it is
possible to guarantee that the decomposed $S_{b}^{*}$ only includes edges $e$
for which $sm\\_eq(e,G_{b})\subseteq sm\\_eq(e,G_{b}^{*})$, then by Lemma 1,
the following inequality holds:

$inc\\_cost(S^{*}_{b},G_{b})\leq inc\\_cost(S^{*}_{b},G^{*}_{b}).$ (1)

Since $S_{b}$ is chosen by $raise\\_mst$ to be an optimal set to lift, it
follows that $raise\\_mst$ is as good as an optimal solution. More
specifically, between budget $b$ and $b+\epsilon$ for some $\epsilon>0$,
spending $\epsilon$ to uniformly lift the set $S^{*}_{b}$ increases the MST in
$G_{b}^{*}$ by $\frac{\epsilon}{inc\\_cost(S^{*}_{b},G_{b}^{*})}$. From
inequality (1), this value is at most
$\frac{\epsilon}{inc\\_cost(S^{*}_{b},G_{b})}$, which is at most
$\frac{\epsilon}{inc\\_cost(S_{b},G_{b})}$ due to the choice of $S_{b}$ by
$raise\\_mst$. Hence, spending $\epsilon$ on $S_{b}$ in $G_{b}$ is as
worthwhile as spending it on $S_{b}^{*}$ in $G_{b}^{*}$. However, this
argument relies on the subtle fact that $S_{b}^{*}$ is lifted by the same
amount $\epsilon/c(S^{*}_{b})$ on every edge. We will see that in the proposed
decomposition of the optimal solution in [12], the $S_{b}^{*}$’s are not
lifting sets in this way.

Here is the definition of $S_{b}^{*}$ in [12]: Given $0<b<B$, for $\Delta>0$,
let $c_{\Delta}$ be the total cost of bringing all edges from its initial
weight of $w(e)$ to $\min\\{w^{*}(e),w_{b}(e)+\Delta\\}$. Let $\Delta_{b}$ be
such that $c_{\Delta_{b}}=b$ and let
$w^{*}_{b}(e)=\min\\{w^{*}(e),w_{b}(e)+\Delta_{b}\\}$ for all edges $e$.
Select $S^{*}_{b}$ to include all of the edges $e$ for which
$w_{b}^{*}(e)=w_{b}(e)+\Delta_{b}\leq w^{*}(e)$ and
$w^{*}_{b-\epsilon}(e)<w^{*}(e)$ for all $b\geq\epsilon>0$.

#### Counterexample showing $S^{*}_{b}$ is not a lift.

Consider a path with three edges $e_{1}$, $e_{2}$ and $e_{3}$ whose initial
weights are $0$. Assume the unit cost of raising the weight of any edge is
$1$. For $B=4$, let $w^{*}=(1,2,1)$ and $w=(2,2,0)$ be their final weight in
an optimal solution and $raise\\_mst$ respectively. Furthermore, assume
$raise\\_mst$ simply found the set $\\{e_{1},e_{2}\\}$ and raised its weight
by $2$ until all the budget is spent. Following the definition in [12],
$S_{b}=\\{1,2\\}$ for all $0\leq b\leq 4$. Recall that
$w^{*}_{b}=min(w^{*},w_{b}+\Delta_{b})$ with $\Delta_{b}$ such that the cost
of increasing to these weights would be $b$.

Then $w^{*}_{2}=(1,1,0)$. When $b=2+\epsilon$,
$w_{b}=(1+\epsilon/2,1+\epsilon/2,0)$. Due to the cap imposed by $w$,
$w^{*}_{2+\varepsilon}=(\min(1,1+\epsilon/2+\Delta_{2+\epsilon}),\min(2,1+\epsilon/2+\Delta_{2+\epsilon}),\min(1,0+\Delta_{2+\epsilon}))=(1,1+\epsilon/2+\Delta_{2+\epsilon},\Delta_{2+\epsilon})$.
Thus, by setting $\Delta_{2+\epsilon}=\epsilon/4$, we achieve a weight of
$w_{2+\epsilon}=(1,1+\frac{3\varepsilon}{4},\frac{\varepsilon}{4})$, spending
a total budget of $2+\epsilon$. We see that the lifting set
$S^{*}_{2+\varepsilon}$ should be $\\{e_{2},e_{3}\\}$. However, $e_{2}$ and
$e_{3}$ are not lifted by the same amount. Thus, it is unclear how much
improvement was achieved by the optimal solution in the range of
$(w,w+\epsilon)$, making it incomparable to $raise\\_mst$.

######  Remark 1.

We notice that an analogous proof is given in [13] in section 3.1 in the
context of matroids. This proof contains the same problem, and the following
correction can also be applied.

#### A Corrected Decomposition.

We now provide a valid decomposition of an optimal solution, leading to a
correct proof of the same result.

For any real number $0\leq b\leq B$, let $S_{b}$ denote the edge set lifted by
$raise\\_mst$ after spending budget $b$. Let $G_{b}=(V,E,w_{b})$, the state of
the graph produced by the algorithm at budget $b$. More precisely, $S_{b}$ is
the set of edges lifted in the $j$-th iteration where $j$ is the largest
integer such that the budget spent at the beginning of the iteration is less
or equals to $b$. Note that $raise\\_mst$ lifts an edge set until it reaches
its tolerance. Since all initial weights are integral, the tolerance of a set
can only change once its weight were increased to the next integral value.

Then, let $b_{0}=0$, $b_{1},...,b_{k-1},b_{k}=B$ be the sequence of budget
values that the algorithm $raise\\_mst$ spends such that between any
consecutive values, the difference was spent by $raise\\_mst$ to lift the
weight of an edge set to the next integral amount (or until out of budget).
This implies that after spending budget $b_{i}$, an additional $b_{i+1}-b_{i}$
budget is used to increase the weight of an edge set $S_{b_{i}}$ by one unit,
or possibly less because we ran out of budget. Let $w_{b}(e)$ denote the
weight of edge $e$ after spending budget $b$. Then for $e\in
S_{b_{i}},e^{\prime}\notin S_{b_{i}}$, the weight of $e^{\prime}$ does not
change as budget increases from $b_{i}$ to $b_{i+1}$, i.e.
$w_{b_{i}}(e^{\prime})=w_{b_{i+1}}(e^{\prime})$. Furthermore, since
$w_{b_{i}}(e^{\prime})$ is an integer, it is not strictly between the interval
$(w_{b_{i}}(e),w_{b_{i+1}}(e))$.

Given an optimal solution, let $w^{*}$ represent the final weights of the
edges. On a high level, we will decompose this optimal solution into a
sequence of lifts by following $raise\\_mst$ as closely as possible. At some
budget $b$, an edge might reach its final weight $w^{*}$ and we must find an
alternative way to spend the excess budget. Thus, we raise the rest of the
edges in $S_{b}$ faster, until they reach what they are supposed to be
relative to how much $raise\\_mst$ has spent its budget. Lastly, if any excess
budget remains, it is spent on lifting all edges (that are not yet capped) by
the same amount $\Delta$. Then, the weight of any edge after spending budget
$b$ in our decomposition has two components, $w_{b}$, the amount from
emulating $raise\\_mst$, and a global increase of $\Delta$.

In order to explicitly define the weight of an edge in our decomposition after
spending budget $b$, let $c_{\Delta,b}(e)$ be the cost to increase an edge $e$
with initial weight $w(e)$ to $min(w^{*}(e),w_{b}(e)+\Delta)$. Lightly abusing
the notation, let $c_{\Delta,b}=\sum_{e\in E(G)}c_{\Delta,b}(e)$. Note that
when $\Delta=0$, due to the cap imposed by $w^{*}$, we might no longer need to
spend all of the budget $b$ and thus $c_{0,b}\leq b$. Also, when there are no
caps imposed by $w^{*}$, we have $c_{0,b}=b$.

Ideally, we would like $c_{\Delta,b}=b$ because it is easier compare how the
optimal and $raise\\_mst$ spend the budget. Thus, for $0\leq i<k$, let
$\Delta_{i}$ be a value such that $c_{\Delta_{i},b_{i}}=b_{i}$. Informally,
since some edges get capped by $w^{*}$, simply raising the weight of edges to
$w_{b_{i}}$ might cost less than $b_{i}$. Then, $\Delta_{i}$ represents how
much extra global weight we have to increase every non-capped edge in order to
match the spending of $b_{i}$.

First, we show the following claim:

######  Claim.

$\\{\Delta_{i}\\}_{i=0}^{k-1}$ is a non-decreasing sequence.

###### Proof.

We will show that $\Delta_{i+1}\geq\Delta_{i}$. Consider the difference
between $b_{i}=c_{\Delta_{i},b_{i}}$ and $c_{\Delta_{i},b_{i+1}}$. To achieve
the second cost, the weight of some of the edges is increased to
$w_{b_{i+1}}$. Since some of edges might get capped, the change in weight is
at most $w_{b_{i+1}}-w_{b_{i}}$. Since $raise\\_mst$ spends $b_{i+1}-b_{i}$ to
change the edges from weight $w_{b_{i}}$ to $w_{b_{i+1}}$, the difference in
the two above costs is at most $b_{i+1}-b_{i}$. Then,
$c_{\Delta_{i},b_{i+1}}\leq
c_{\Delta_{i},b_{i}}+(b_{i+1}-b_{i})=b_{i+1}=c_{\Delta_{i+1},b_{i+1}}$. Thus,
it follows that $\Delta_{i+1}\geq\Delta_{i}$. ∎

Note that after spending budget $b_{i}$, we should expect our decomposition of
the optimal solution to ensure each edge has weight
$\min\\{w^{*}(e),w_{b_{i}}(e)+\Delta_{i}\\}$. Then, between a budget spending
of $b_{i}$ and $b_{i+1}$,the weight of an uncapped edge in the decomposition
should grow from $w_{b_{i}}(e)+\Delta_{i}$ to $w_{b_{i+1}}(e)+\Delta_{i+1}$.
To achieve this increase, we break each interval $[b_{i},b_{i+1}]$ of the
budget-spending process into two phases. In the first phase, we spend the
increase in budget to augment the weight of edges from $w_{b_{i}}+\Delta_{i}$
to $w_{b_{i+1}}+\Delta_{i}$. Then, in the second phase, we increase their
weight from $w_{b_{i+1}}(e)+\Delta_{i}$ to $w_{b_{i+1}}(e)+\Delta_{i+1}$. Let
$\beta_{i}=c_{\Delta_{i},b_{i+1}}$, representing the transitioning point (in
terms of the budget) between the two phases.

We then define $w^{*}_{b}$.

######  Definition 1.

The edge weight $w^{*}_{b}(e):=$

  * •

$min(w^{*}(e),w_{f(b)}(e)+\Delta_{i})$, with $f:\mathbb{R}\to\mathbb{R}$ such
that $c_{\Delta_{i},f(b)}=b$, for $b\in[b_{i},\beta_{i}]$,

  * •

$min(w^{*}(e),w_{b_{i+1}}+\Delta(b))$, with $\Delta(b)$ such that
$c_{\Delta(b),b_{i+1}}=b$, for $b\in[\beta_{i},b_{i+1}]$,

######  Claim.

The following holds:

  1. 1.

$f(b_{i})=b_{i}$ and $f(\beta_{i})=b_{i+1}$,

  2. 2.

$f(b)$ is an increasing function in the interval $[b_{i},\beta_{i}]$

  3. 3.

$\Delta(\beta_{i})=\Delta_{i}$ and $\Delta(b_{i+1})=\Delta_{i+1}$, and

  4. 4.

$\Delta(b)$ is an increasing function in the interval $[\beta_{i},b_{i+1}]$.

###### Proof.

The first statement follows from the definition of $\Delta_{i}$ and
$\beta_{i}$. To prove the second statement, consider $b,b^{\prime}$ such that
$b_{i}\leq b<b^{\prime}\leq\beta_{i}$. Note that $c_{\Delta_{i},f(b)}$ and
$c_{\Delta_{i},f(b^{\prime})}$ corresponds to the cost of raising edges to a
weight of $\min\\{w^{*}(e),w_{f(b)}+\Delta_{i}\\}$ and
$\min\\{w^{*}(e),w_{f(b^{\prime})}+\Delta_{i}\\}$. Since by definition,
$c_{\Delta_{i},f(b)}=b<b^{\prime}=c_{\Delta_{i},f(b^{\prime})}$, it follows
that there exists some edge $e$ such that $w_{f(b)}(e)<w_{f(b^{\prime})}(e)$.
Since $w_{b^{\prime\prime}}(e)$ is non decreasing with respect to
$b^{\prime\prime}$, it follows that $f(b)<f(b^{\prime})$, proving the second
statement.

The third statement follows from the definition of $\beta_{i}$ and
$\Delta_{i+1}$. For the fourth statement, we use similar arguments as the
proof for the second statement. Consider $b,b^{\prime}$ such that
$\beta_{i}\leq b<b^{\prime}\leq b_{i+1}$. Since $c_{\Delta(b),b_{i+1}}$
corresponds to the cost of raising edges to a weight of
$\min\\{w^{*}(e),w_{b_{i+1}}+\Delta(b)\\}$, does not increase if $\Delta(b)$
does not increase. Then, to achieve a higher cost of $b^{\prime}$, it follows
that $\Delta(b^{\prime})<\Delta(b)$.

∎

######  Remark 2.

If we extend the definition of $f(b)$ and $\Delta(b)$ to $f(b)=b$ for
$b\in[\beta_{i},b_{i+1}]$ and $\Delta(b)=\Delta_{i}$ for
$b\in[b_{i},\beta_{i}]$, then $f(b)$ and $\Delta(b)$ become two non-decreasing
continuous functions. Furthermore, we have that
$w^{*}_{b}(e)=min(w^{*}(e),w_{f(b)}(e)+\Delta(b))$ and $w^{*}_{b}(e)$ is also
a non-decreasing function. It is also clear that after spending a total budget
of $B$, all edges should reach its desired maximum weight of $w^{*}$.

Here is an intuitive explanation of $f(b)$ and $\Delta(b)$. During the first
phase, the decomposition would like to copy $raise\\_mst$ and lift all the
edges in $S_{b_{i}}$. However, at some point, an edge $e\in S_{b_{i}}$ might
have reached its full capacity $w^{*}$. Then, in order to match the same
amount of spending as $raise\\_mst$, we would need to raise the rest of the
edges in $S_{b_{i}}$ at a faster rate. Thus, to actually spend budget $b$, we
had to lift some edges higher, to a point where if all edges in $S_{b_{i}}$
were raised to that point would have costed us $f(b)$. Similarly, $\Delta(b)$
is an adjustment function, corresponding to a faster rate of increasing
$\Delta$ in the second phase, caused by some edges reaching its full capacity.

#### Example of the Correct Decomposition

: Consider performing the above decomposition on our previous counter-example.
Recall that $G$ is a path of three edges whose initial weights are $0$. With a
total budget of $4$, $raise\\_mst$ lifts $e_{1},e_{2}$ by $2$ to a final
weight of $(2,2,0)$ for edges $(e_{1},e_{2},e_{3})$. An optimal solution has a
final weight of $(1,2,1)$. By definition, $b_{0}=0,b_{1}=2,b_{2}=4$ where the
set $S=\\{e_{1},e_{2}\\}$ is first raised to weight $1$ then raised to weight
$2$. Since $c_{0,b_{0}}=0=b_{0}$, $\Delta_{0}=0$. Between $b_{0}$ and $b_{1}$,
our decomposition would copy $raise\\_mst$ exactly, so $f(b)=b,\Delta(b)=0$
for $b_{0}\leq b\leq b_{1}$. Note that $\beta_{0}=b_{1}$ and $\Delta_{1}=0$
since there is no second phase in this interval. See Figure 1.

Now, consider when $b\in[b_{1},b_{2}]$. Note that $c_{1,b_{2}}$ is the cost of
raising the weights to $(\min(1,3),\min(2,3),\min(1,1))=(1,2,1)$. Then,
$c_{1,b_{2}}=4=b_{2}$ and therefore $\Delta_{2}=1$. Note that
$\beta_{1}=c_{\Delta_{1},b_{2}}$ is the cost of reaching a weight of $(1,2,0)$
and thus $\beta_{1}=3$. In the first phase, since $e_{1}$ is already capped,
$c_{0,b^{\prime}}$ is the cost of reaching a weight of $(1,b^{\prime}/2,0)$.
Therefore $c_{\Delta_{1},b^{\prime}}=b^{\prime}/2+1$. In $raise\\_mst$, after
spending budget $b$ to ensure $c_{\Delta_{1},f(b)}=b$, $f(b)=2b-2$. Then,
$w^{*}_{b}=\min(w^{*},w_{f(b)})=(1,b-1,0)$, corresponding to spending the
current increase in budget to raise $e_{2}$’s weight from $1$ to $2$. In the
second phase, for $3=\beta_{1}\leq b\leq b_{2}=4$, note that
$c_{\Delta^{\prime},b_{2}}$ is the cost of raising the weights to
$(1,2,\Delta^{\prime})$. Then, $c_{\Delta^{\prime},b_{2}}=3+\Delta^{\prime}$.
To ensure $c_{\Delta(b),b_{2}}=b$, we see that $\Delta(b)=b-3$. Then,
$w^{*}_{b}=(1,2,b-3)$ corresponding to lifting the weight of $e_{3}$ from $0$
to $1$. Note that now each step of the decomposition corresponds to a proper
lift. More precisely, between $[b_{1},\beta_{1}]$, only edge $e_{2}$ is lifted
and between $[\beta_{1},b_{2}]$ only edge $e_{3}$ is lifted.

b$b_{1}=2$$\beta_{1}=3$$b_{2}=4$$f(b_{1})$$f(\beta_{1})=f(b_{2})$$f(b)$$\Delta_{2}=1$$\Delta_{0},\Delta_{1}=0$$\Delta$
Figure 1: The functions $f$ (in red) and $\Delta$ (in blue) in the case of the
previously discussed counter-example.

#### The new decomposition provides lifts

: We now show that if we view the optimal solution as a continuous process
that increases the weights of edges according to $w^{*}_{b}$, then the
decomposition produces a sequence of lifts. For any $0\leq b<B$, let
$S^{*}_{b}$ be the set of edges whose weight changes at budget $b$ according
to $w^{*}_{b}$. Formally,
$S^{*}_{b}=\\{e:w^{*}_{b}(e)<w^{*}_{b+\epsilon}(e)\forall\epsilon>0\\}$.

However, when lifting from $b_{i}$ to $\beta_{i}$ (or from $\beta_{i}$ to
$b_{i+1}$), we may however be lifting different sets. Indeed, we could hit one
of the upper bounds for one of the edges that we are lifting during this
period, and so the set we are lifting would shrink to another, smaller set.
This is why we now introduce new breakpoints $(p^{i}_{j})$ in between the
$b_{i}$s and $\beta_{i}$s, in order to always have proper lifts, which will
guarantee that we can indeed compare the optimal solution to the solution
given by $raise\\_mst$.

######  Lemma 2.

For every $0\leq i<k$, there exists a finite sequence
$\\{p^{i}_{j}\\}^{l}_{j=0}$ where $p^{i}_{0}=b_{i}$, $p^{i}_{l}=b_{i+1}$ and
there exists $0\leq k\leq l$ such that $p^{i}_{k}=\beta_{i}$. Furthermore, for
any interval $[p^{i}_{j},p^{i}_{j+1}]$, the set of edges whose weights changed
according to $w^{*}_{b}$ when $b$ is within this interval corresponds to a
proper lift. More precisely, for all $p^{i}_{j}\leq b<p^{i}_{j+1}$, we have
that $S^{*}_{b}=S^{*}_{p_{j}}$ and
$w^{*}_{b}(e)-w^{*}_{p_{j}}(e)=w^{*}_{b}(e^{\prime})-w^{*}_{p_{j}}(e^{\prime})$
for any $e,e^{\prime}\in S^{*}_{b}$.

###### Proof.

Fix $0\leq i<k$. We find the sequence separately for each of the two phases.
Suppose we are in the first phase where $b_{i}\leq b\leq\beta_{i}$. Let
$b_{i}<p_{1}<p_{2}<...<\beta_{i}$ be a sequence of budgets at which some edge
reaches its cap. Formally, $p_{j}$ is in the sequence if there exists an edge
$e$ such that $w^{*}_{p_{j}-\epsilon}(e)<w^{*}_{p_{j}}(e)=w^{*}(e)$ for all
$\epsilon>0$. Note that since there are only finitely many edges and each edge
can reach its maximum cap only once, this sequence is finite. We claim that
within the interval $(p_{j},p_{j+1})$, edges are being properly lifted with
respect to $w_{b}^{*}$.

Let $p_{j}\leq b<b^{\prime}\leq p_{j+1}$. Let
$P^{*}=\\{e:w^{*}_{p_{j}}(e)=w^{*}(e)\\}$, representing the set of all edges
that reached its maximum cap at budget $p_{j}$. First we show
$S^{*}_{b}=S_{b_{i}}\setminus P^{*}$. Let $e\in S^{*}_{b}$. Since no edges
becomes capped between $p_{j}$ and $p_{j+1}$, it follows that
$w^{*}_{b}=w_{f(b)}(e)+\Delta_{i}$ and
$w^{*}_{e}=w_{f(b^{\prime})}+\Delta_{i}$. By definition of $S^{*}_{b}$, it
follows that $w^{*}_{b}<w^{*}_{b^{\prime}}$. From Claim 2.2, we know
$b_{i}\leq f(b)<f(b^{\prime})\leq b_{i+1}$. Then, $w_{b_{i}}(e)\leq
w_{f(b)}(e)<w_{f(b^{\prime})}(e)\leq w_{b_{i+1}}(e)$. Thus, the weight of edge
$e$ changed with respect to $w_{b}$, proving $e\in S_{b_{i}}$. Since
$w^{*}_{b}(e)<w^{*}_{b^{\prime}}(e)$, it also follows that $e$ does not become
capped at nor before $b$, proving $e\notin C^{*}$. Thus, $S_{b}^{*}\subseteq
S_{b_{i}}\setminus C^{*}$.

For the other direction, let $e^{\prime}\in S_{b_{i}}\setminus C^{*}$. Since
$e^{\prime}$ does not get capped,
$w^{*}_{b}(e^{\prime})=w_{f(b)}(e^{\prime})+\Delta_{i}$ and
$w^{*}_{b^{\prime}}(e^{\prime})=w_{f(b^{\prime})}(e^{\prime})+\Delta_{i}$.
From Claim 2.2, since $b_{i}\leq f(b)<f(b^{\prime})\leq b_{i+1}$, it follows
that $w_{f(b)}(e^{\prime})<w_{f(b^{\prime})}(e^{\prime})$ and thus
$w^{*}_{b}(e)<w^{*}_{b^{\prime}}(e)$. Since this inequality holds for any
$b^{\prime}<b^{\prime\prime}<b_{i+1}$, it follows that
$w^{*}_{b}(e)<w^{*}_{b+\epsilon}(e)$ for all $\epsilon>0$, proving $e\in
S^{*}_{b}$. Thus, we conclude that $S^{*}_{b}=S^{*}_{p_{j}}=S_{b_{i}}\setminus
P^{*}$.

Let $e,e^{\prime}\in S^{*}_{b}$. Since $e$ is not capped,
$w^{*}_{b}(e)-w^{*}_{p_{j}}(e)=w_{f(b)}(e)-w_{f(p_{j})}(e)$. Since
$e,e^{\prime}\in S^{*}_{b}\subseteq S_{b_{i}}$, $raise\\_mst$ lifts their
weight by the same amount in the interval $[b_{i},b_{i+1}]$. Since
$b\in[b_{i},b_{i+1}]$, it follows that
$w_{f(b)}(e)-w_{f(p_{j})}(e)=w_{f(b)}(e^{\prime})-w_{f(p_{j})}(e^{\prime})$,
proving our lemma holds for the first phase.

For the second phase of the interval when $\beta_{i}\leq b<\beta_{i+1}$, let
$\beta_{i}<q_{1}<q_{2}<...<b_{i+1}$ be a sequence of budgets such that some
edge $e$ becomes capped at budget $q_{j}$. Once again, this sequence is
finite. Let $q_{j}\leq b<q_{j+1}$. Since no edges becomes capped,
$w^{*}_{b}(e)=w_{b_{i+1}}(e)+\Delta(b)$ holds for any $e\in S^{*}_{b}$. From
Claim 2.2, since $\Delta(b)$ is an increasing function, it follows that
$w^{*}_{b}$ increases for all non-capped edge $e$. Since no new edges become
capped, $S^{*}_{b}=S^{*}_{q_{j}}$. It also follows that for any edge $e\in
S^{*}_{b}$, $w^{*}_{b}(e)-w^{*}_{q_{j}}(e)=\Delta(b)-\Delta(q_{j})$, proving
the lemma also holds for the second phase.

∎

Let $P^{*}_{b}=\\{e:w^{*}_{b}(e)=w^{*}(e)\\}$, representing the set of edges
that reached its cap at budget $b$. The next corollary follows from the proof
of the previous lemma.

######  Corollary 1.

For an interval $[b_{i},b_{i+1}]$, given the finite sequence $\\{p^{i}_{j}\\}$
from above, we can explicitly describe $S^{*}_{p^{i}_{j}}$. In particular:

  * •

if $b_{i}\leq p^{i}_{j}<p^{i}_{j+1}\leq\beta_{i}$, then
$S^{*}_{p^{i}_{j}}=S_{b_{i}}\setminus P^{*}_{p^{i}_{j}}$,

  * •

if $\beta_{i}\leq p^{i}_{j}<p^{i}_{j+1}\leq b_{i+1}$, then
$S^{*}_{p^{i}_{j}}=E(G^{*})\setminus P^{*}_{p^{i}_{j}}$.

Now, we prove the correctness of the algorithm.

######  Theorem 2.1.

The algorithm raise_mst gives an optimal increase for continuous MMST.

###### Proof.

The strategy of the proof is the same as the one in [12]. We compare the
lifted sets $S_{b_{i}}$ in $raise\\_mst$ to the ones obtained from our
decomposition, $S^{*}_{b}$. Given $0\leq i<k$, let $\\{p_{k}\\}$ be the finite
sequence defined in the previous lemma (we drop the superscript $i$ for
convenience). We now show that for any interval $[p_{j},p_{j+1}]$, lifting
$S_{p_{j}}=S_{b_{i}}$ in $raise\\_mst$ increases the MST of $G_{p_{j}}$ by at
least as much as the increase in MST of $G^{*}_{p_{k}}$ caused by lifting
$S^{*}_{p_{j}}$ in our decomposition.

If the lift was performed in the first phase where $b_{i}\leq
p_{j}<p_{j+1}\leq\beta_{i}$, then by Corollary 1, $S^{*}_{p_{j}}\subseteq
S_{p_{j}}=S_{b_{i}}$. Let $e\in S^{*}_{p_{j}},e^{\prime}\in
sm\\_eq(e,G_{p_{j}})$. By Corollary 1, $e\in S_{b_{i}}$ and thus
$w_{b_{i}}(e)\leq w_{b}(e)<w_{b_{i+1}}(e)$ for all $b_{i}\leq b<b_{i+1}$. We
claim that $w_{b}(e^{\prime})\leq w_{b}(e)$ for all $b_{i}\leq b\leq b_{i+1}$.
If $e^{\prime}\in S_{b_{i}}$, since $raise\\_mst$ only lifts edges of the same
weight, $w_{b}(e^{\prime})=w_{b}(e)$. If $e^{\prime}\notin S_{b_{i}}$, then
$w_{b}(e^{\prime})=w_{b_{i}}(e^{\prime})$. By our choice of $b_{i}$,
$w_{b_{i+1}}(e)\leq w_{b_{i}}(e)+1$. Then, $e^{\prime}\in
sm\\_eq(e,G_{p_{j}})$ implies $w_{p_{j}}(e^{\prime})\leq\lfloor
w_{p_{j}}(e)\rfloor=w_{b_{i}}(e)\leq w_{b}(e)$, proving our claim.

It follows by definition of $w_{p_{j}}^{*}$ and $S_{p_{j}}^{*}$ that
$w_{p_{j}}^{*}(e)=w_{f(p_{j})}(e)+\Delta_{i}$ and
$w_{p_{j}}^{*}(e^{\prime})\leq w_{f(p_{j})}(e^{\prime})+\Delta_{i}$. Note that
since $p_{j}<\beta_{i}$, $f(p_{j})<b_{i+1}$ by Claim 2.2. Then, using the
claim in the previous paragraph, $w_{f(p_{j})}(e^{\prime})\leq
w_{f(p_{j})}(e)$, proving that $w^{*}_{p_{j}}(e^{\prime})\leq
w^{*}_{p_{j}}(e)$. Therefore, $e^{\prime}\in sm\\_eq(e,G^{*}_{p_{j}})$ and
$sm\\_eq(e,G_{p_{j}})\subset sm\\_eq(e,G^{*}_{p_{j}})$. Then, by Lemma 1,
$coverage(S_{b}^{*},G_{b}^{*})\leq coverage(S_{b}^{*},G_{f(b)})$, and

$\begin{split}inc\\_cost(S_{p_{j}},G_{p_{j}})&\leq
inc\\_cost(S_{p_{j}}^{*},G_{p_{j}})\quad\mbox{by the optimal choice of
$S_{p_{j}}=S_{b_{i}}$}\\\
&=\frac{c(S_{p_{j}}^{*})}{coverage(S_{p_{j}}^{*},G_{p_{j}})}\\\
&\leq\frac{c(S_{p_{j}}^{*})}{coverage(S_{p_{j}}^{*},G^{*}_{p_{j}})}=inc\\_cost(S_{p_{j}}^{*},G_{p_{j}}^{*})\end{split}$

This implies after spending the same amount of budget $p_{j+1}-p_{j}$,
$raise\\_mst$ increased the MST value by at least as much as what the optimal
solution did in their respective graphs.

Now, suppose the lift occurred in the second phase where $\beta_{i}\leq
p_{j}<p_{j+1}\leq b_{i+1}$. Let $e\in S_{p_{j}}$ and $e^{\prime}\in
sm\\_eq(e,G_{p_{j}})$. By Corollary 1, $e$ is an edge that is not capped after
spending budget $p_{j}$. We claim that $w_{b_{i+1}}(e^{\prime})\leq
w_{b_{i+1}}(e)$. If $e^{\prime}\in S_{p_{j}}$, then
$w_{b_{i+1}}(e^{\prime})=w_{b_{i+1}}(e)$ since both edges are lifted together
by $raise\\_mst$. If $e^{\prime}\notin S_{p_{j}}$, then
$w_{b_{i+1}}(e^{\prime})=w_{p_{j}}(e^{\prime})\leq w_{p_{j}}(e)\leq
w_{b_{i+1}}(e)$, proving our claim.

By definition of $w_{b}^{*}$ and $S_{b}^{*}$, it follows that
$w_{p_{j}}^{*}(e)=w_{b_{i+1}}(e)+\Delta(p_{j})$ and
$w_{p_{j}}^{*}(e^{\prime})\leq w_{b_{i+1}}(e^{\prime})+\Delta(p_{j})$. Thus it
follows that $w^{*}_{p_{j}}(e^{\prime})\leq w^{*}_{p_{j}}(e)$ and
$w_{b}^{*}(e^{\prime})\leq w_{b}^{*}(e)$. Then, by Lemma 1, we can conclude
that $coverage(S_{p_{j}}^{*},G_{p_{j}}^{*})\leq
coverage(S_{p_{j}}^{*},G_{p_{j}})$. As before,

$\begin{split}inc\\_cost(S_{p_{j}},G_{p_{j}})&\leq
inc\\_cost(S_{p_{j}}^{*},G_{p_{j}})\quad\text{by optimality of $S_{p_{j}}$}\\\
&=\frac{c(S_{p_{j}}^{*})}{coverage(S_{p_{j}}^{*},G_{p_{j}})}\\\
&\leq\frac{c(S_{p_{j}}^{*})}{coverage(S_{p_{j}}^{*},G^{*}_{p_{j}})}=inc\\_cost(S_{p_{j}}^{*},G_{p_{j}}^{*})\end{split}$

Then once again, by spending the same budget $p_{j+1}-p_{j}$, $raise\\_mst$
increases the MST value by at least as much as the optimal solution. Then, it
follows the total increase of MST performed by $raise\\_mst$ is also optimal.

∎

##  3 Approximating Unit Perturbation MMST

In this section, we present approximation algorithms for both the targeted and
budgeted versions of MMST.

###  3.1 A $2(1-\frac{1}{n})$-Approximation Algorithm for Targeted MMST

######  Theorem 3.1.

Targeted MMST permits a $2(1-\frac{1}{n})$-approximation algorithm.

###### Proof.

The algorithm in [12] computes in strongly polynomial time the function
$f(B)$, the maximum weight of the minimum spanning trees of a graph attainable
by spending a budget of value $B$ to increase the weights of its edges,
potentially in fractional increments. Given a target $T\in\mathbb{N}$, let
$B_{T}$ such that $f(B_{T})=T$. Clearly, $B_{T}$ is a lower bound of the
optimal value for (discrete) unit perturbation to reach MST target weight of
$T$.

We will follow the algorithm in [12] with budget $B_{T}$. Note that the
algorithm lifts edges to their tolerance as long as there is enough budget to
do so. Since the tolerances are integral, all edges are lifted an integral
amount except for possibly the very last lift. Let $S$ denote the last set of
edges computed by this algorithm and balance denote the remaining budget. The
set $S$ induces a partition $P_{1},\ldots,P_{k}$ of some graph
$\tilde{G}_{w_{l}}$. In the last iteration, the algorithm in [12] lifts all
the edges in $S$ by $\frac{balance}{c(S)}$. The weight of the minimum spanning
trees increases by $coverage(S,G)\frac{balance}{c(S)}\in\mathbb{N}$ since
$T\in\mathbb{N}$. If $\frac{balance}{c(S)}\in\mathbb{N}$, then we are done.
Otherwise, we first lift all the edges in $S$ by
$\lfloor\frac{balance}{c(S)}\rfloor$. Then, it remains to increase the weight
of the minimum spanning trees by

$coverage(S,G)(\frac{balance}{c(S)}-\lfloor\frac{balance}{c(S)}\rfloor)<coverage(S,G)=coverage(S,\tilde{G}_{w_{l}})=k-1.$

The remaining budget $R$ is

$R=balance-c(S)\lfloor\frac{balance}{c(S)}\rfloor=c(S)(\frac{balance}{c(S)}-\lfloor\frac{balance}{c(S)}\rfloor).$
(2)

Assume that the node sets $P_{i}$ corresponding to the shores of the partition
are ranked by increasing costs $c(\delta(P_{i}))$. Choose the
$q=coverage(S,G)(\frac{balance}{c(S)}-\lfloor\frac{balance}{c(S)}\rfloor)$
cheapest shores $P_{1},\ldots,P_{q}$ and lift all the edges in
$\delta(P_{1}),\ldots,\delta(P_{k})$ by one. Since
tolerance$(S,G)\geq\frac{balance}{c(S)}>\lfloor\frac{balance}{c(S)}\rfloor$,
it follows that the weight of the minimum spanning trees increases by at least
$q$. By the choice of the sets $P_{1},\ldots,P_{q}$, we have

$\frac{1}{q}\sum_{i=1}^{q}c(P_{i})\leq\frac{1}{k}\sum_{i=1}^{k}c(P_{i})=\frac{2c(S)}{k}.$

This yields

$\displaystyle\sum_{i=1}^{q}c(P_{i})$ $\displaystyle\leq\frac{2q}{k}c(S)$
$\displaystyle=\frac{2coverage(S,G)}{k}(\frac{balance}{c(S)}-\lfloor\frac{balance}{c(S)}\rfloor)c(S)$
$\displaystyle=\frac{2(k-1)}{k}(\frac{balance}{c(S)}-\lfloor\frac{balance}{c(S)}\rfloor)c(S)$
$\displaystyle\leq\frac{2(n-1)}{n}(\frac{balance}{c(S)}-\lfloor\frac{balance}{c(S)}\rfloor)c(S)$
$\displaystyle=\frac{2(n-1)}{n}R.$

Therefore, the total cost used by the approximation algorithm to reach MST
target weight of $T$ is bounded by

$\displaystyle B_{T}-R+\sum_{i=1}^{q}c(P_{i})$ $\displaystyle\leq
B_{T}-R+\frac{2(n-1)}{n}R$ $\displaystyle=B_{T}+(1-\frac{2}{n})R$
$\displaystyle\leq 2(1-\frac{1}{n})B_{T}.$

The theorem follows immediately.

∎

###  3.2 An $\frac{opt}{2}-1$-Solution for Budgeted MMST

Recall that in an $\frac{opt}{2}-1$-solution, the increase in the weight of
the MST is at least $\frac{opt}{2}-1$, where $opt$ is the optimal increase in
the weight of the MST for the given budget $B$.

######  Theorem 3.2.

Budgeted MMST has a polynomial-time algorithm that produces an
$\frac{opt}{2}-1$ solution, where $opt$ is the optimal increase in weight of
the MST.

###### Proof.

Again, we follow the algorithm in [12]. Let $S$ denote the last set of edges
computed by this algorithm and balance denote the remaining budget. The set
$S$ induces a partition $P_{1},\ldots,P_{k}$ of some graph
$\tilde{G}_{w_{l}}$. In the last iteration, the algorithm in [12] lifts all
the edges in $S$ by $\frac{balance}{c(S)}$. If
$\frac{balance}{c(S)}\in\mathbb{N}$, then we are done. Otherwise, we lift all
the edges in $S$ by $\lfloor\frac{balance}{c(S)}\rfloor$.

After this lifting operation, the remaining budget $R$ is defined in (2) and
the weight of the minimum spanning trees increases by

$A+coverage(S,G)\lfloor\frac{balance}{c(S)}\rfloor,$

where $A$ denotes the total increase in the MST weight before lifting $S$.
Therefore, the remaining increase $I$ of the weight of the minimum spanning
trees in comparison with the algorithm in [12] is

$I=coverage(S,G)(\frac{balance}{c(S)}-\lfloor\frac{balance}{c(S)}\rfloor).$

Since the algorithm in [12] optimally uses the budget fractionally, the
optimal increase in the MST using continuous expenditure of the budget $B$ is

$A+coverage(S,G)\lfloor\frac{balance}{c(S)}\rfloor+I,$

which is an upper bound on $opt$, the optimal increase in the weight of the
MST for the given budget $B$.

Assume that the shores $P_{i}$ are ranked by increasing costs
$c(\delta(P_{i}))$. Suppose first that there exists an index $q$ such that
$c(\delta(P_{1}\cup\cdots\cup P_{q}))\leq R<c(\delta(P_{1}\cup\cdots\cup
P_{q+1}))$. Lift all the edges in $\delta(P_{1}),\ldots,\delta(P_{q})$ by one.
Since
tolerance$(S,G)\geq\frac{balance}{c(S)}>\lfloor\frac{balance}{c(S)}\rfloor$,
it follows that the weight of the minimum spanning trees increases by at least
$q$ in this step.

By the ordering of the node sets $P_{i}$, we have

$\frac{1}{q+1}\sum_{i=1}^{q+1}c(\delta(P_{i}))\leq\frac{1}{k}\sum_{i=1}^{k}c(\delta(P_{i}))=\frac{2c(S)}{k}.$

Therefore,

$\displaystyle q+1$
$\displaystyle\geq\frac{k\sum_{i=1}^{q+1}c(\delta(P_{i}))}{2c(S)}$
$\displaystyle\geq\frac{kc(\delta(P_{1}\cup\cdots\cup P_{q+1}))}{2c(S)}$
$\displaystyle>\frac{kR}{2c(S)}$
$\displaystyle=\frac{k}{2}(\frac{balance}{c(S)}-\lfloor\frac{balance}{c(S)}\rfloor)$
$\displaystyle\geq\frac{coverage(S,G)}{2}(\frac{balance}{c(S)}-\lfloor\frac{balance}{c(S)}\rfloor)$
$\displaystyle=\frac{I}{2}.$ (3)

This implies $q>\frac{I}{2}-1$, and hence the approximation algorithm
increases the weight of the minimum spanning trees increases by at least

$\displaystyle A+coverage(S,G)\lfloor\frac{balance}{c(S)}\rfloor+q$
$\displaystyle>\frac{1}{2}(A+coverage(S,G)\lfloor\frac{balance}{c(S)}\rfloor+I)-1$
$\displaystyle\geq\frac{opt}{2}-1.$

In the case where $c(\delta(P_{1}))>R$, since
$c(\delta(P_{1}))\leq\frac{1}{k}\sum_{i=1}^{k}c(\delta(P_{i}))$, we have

$\frac{kR}{2c(S)}<\frac{kc(\delta(P_{1}))}{2c(S)}\leq 1.$

The inequalities in (3.2) imply that $\frac{I}{2}\leq\frac{kR}{2c(S)}$ and
thus $\frac{I}{2}\leq 1$. Therefore, by doing nothing we are still within an
additive one of the optimal value of $I$.

$\displaystyle A+coverage(S,G)\lfloor\frac{balance}{c(S)}\rfloor$
$\displaystyle\geq
A+coverage(S,G)\lfloor\frac{balance}{c(S)}\rfloor+\frac{I}{2}-1$
$\displaystyle\geq\frac{1}{2}(A+coverage(S,G)\lfloor\frac{balance}{c(S)}\rfloor+I)-1$
$\displaystyle\geq\frac{opt}{2}-1.$

∎

##  4 Hardness of MMST

If we impose upper bounds on the extent to which edge weights can be
increased, we can encode a $k$-cut problem using MMSTU (the version of MMST
with such upper bounds).

######  Lemma 3.

The Budgeted MMSTU problem is NP-complete.

###### Proof.

The problem is clearly in NP. We now reduce min $k$-cut to this problem. Let
$(G,k)$ be an instance of $k$-cut. For every edge $e\in E(G)$, consider
assigning a cost $c(e)\equiv 1$, a weight $w(e)\equiv 0$ and an upperbound
$u(e)\equiv 1$. For $B\in[0,n]$, consider solving the instance of MMSTU with
budget $B$ and let $E_{B}$ be the set of edges giving by the solution that
raises the MST to weight $T_{B}$. Since $G$ starts with a MST of weight $0$
and every edge in $S_{B}$ has a final weight of $1$, it follows that
$coverage(S_{B},G)=T_{B}$. Then,, it follows that the smallest $B$ such that
$T_{B}\geq k-1$ provides a minimum $k$-cut for $G$.

∎

What is perhaps a bit surprising is that even without upper bounds and all
upgrade costs being unit, MMST is NP-hard.

######  Theorem 4.1.

Budgeted MMST is NP-complete even with unit downgrading costs.

###### Proof.

Given an instance of Min $k$-Cut, $(G,k)$, consider the following auxiliary
graph $G^{\prime}$. For every edge $e=uv\in E(G)$, we add a clique of size
$n^{2}$ and add edges from the vertices of the clique to the vertices $u$ and
$v$. Original edges start with weight $0$ and all newly added edges have
weight $1$. The upgrading cost $c$ for all edges is $1$. Note that an initial
MST needs to connect the newly added $n^{2}|E(G)|$ vertices and thus has
weight at least $n^{2}|E|$. An MST of weight $n^{2}|E(G)|$ exists by simply
taking a spanning tree of the original zero-weight edges and greedily
appending the newly added vertices to this spanning tree.

Suppose $F\subseteq E(G)$ is an optimal min $k$-cut and $|F|=b$. Consider
spending $b$ budget to upgrade the edges in $F$ to weight $1$. Since
$G\backslash F$ has $k$ connected components in $G$, all the edges with final
weight of $0$, $E(G)\setminus F$, also forms $k$ connected components in
$G^{\prime}$. Then it follows that has final weight of an MST in $G^{\prime}$
is at least $2n|E|+k-1$. One can also easily construct an MST with such weight
by first taking a maximal forest using the edges in $E(G)\setminus F$, then
add $k-1$ edges in $F$ to form a tree that spas all the original vertices and
lastly greedily append the newly added vertices in the clique. Therefore under
budget $b$, one can increase the MST value by $k-1$. Then, our goal is to find
the least amount of budget $b$ that improves the MST value by $k-1$ and show
such solution can be translated to a $k$-cut.

Consider greedily trying all values of $b$ where $0\leq b\leq|E(G)|<n$ and
solve the instances of MMST on $G^{\prime}$ with budget $b$. Let $b^{\prime}$
be the smallest $b$ such that the solution to MMST increased the MST value by
$k-1$. Such $b^{\prime}$ exists since raising the weight of every original
edge by $1$ increases the MST by at least $n\geq k-1$. —Let $F^{\prime}$ be
the set of edges whose weight was changed by such an optimal solution.

First, we claim that no newly added edge is in $F^{\prime}$. Suppose for the
sake of contradiction that there exists such edge $e^{\prime}\in F^{\prime}$
where $e^{\prime}$ is also in $E(G^{\prime})\setminus E(G)$. Let $T$ be an MST
after upgrading the edges in $F^{\prime}$ to their final weight. Since
$e^{\prime}$ is a newly-added edge, let $e\in E(G)$ be its associated original
edge. Note that the endpoints of $e$ along with the newly-added clique forms a
large clique $K^{\prime}$ of size $n^{2}+2$. Since $|F^{\prime}|\leq
b^{\prime}<n^{2}$, $K^{\prime}\backslash F^{\prime}$ is connected. Then, one
can construct an MST $T^{\prime}$ from $T$ that avoids any edges in $E(K)\cap
F^{\prime}$. Consider the path $P^{\prime}$ in $T^{\prime}$ that connects the
endpoints of $e^{\prime}$. Note that $P^{\prime}$ lies in $K^{\prime}$ and the
final weight of every edge in $P^{\prime}$ is $1$. Then, if we did not upgrade
$e^{\prime}$, the weight of every edge in $P^{\prime}$ is still at most the
weight of $e^{\prime}$. Then, $T^{\prime}$ is also an MST if we do not upgrade
$e^{\prime}$, contradicting the minimum choice of $b^{\prime}$.

Next, we claim that no original edge is upgraded more than once. The argument
is similar to the one before. Suppose for the sake of contradiction that an
edge $e\in E(G)$ is upgraded more than once. Let $K^{\prime}$ be the clique of
size $n^{2}+2$ containing $e$. By similar argument, one can show that there
exists an MST $T^{\prime}$ in $G^{\prime}$ after upgrading such that $e\notin
T^{\prime}$. Then, one can similarly argue that $T^{\prime}$ remains an MST if
$e$ is only upgraded to $1$, contradicting the minimum choice of $b^{\prime}$.

Then, it follows that $|F^{\prime}|=b^{\prime}$. Let $T^{\prime}$ be an MST of
$G^{\prime}$ before upgrading the edges in $F^{\prime}$. Note that
$|E(T^{\prime})\cap F^{\prime}|\geq k-1$ since the weight of the final MST is
increased by at least $k-1$. We claim that
$T=T^{\prime}\backslash(V(G^{\prime})\setminus V(G))$ is a spanning tree of
$G$. Suppose for the sake of contradiction that $T$ is not connected and
contains a cut $\delta(V_{1})$. Since $G$ is connected, there exists
$e\in\delta(V_{1})\cap E(G)$. Let $e^{\prime}\in\delta(V_{1})\cap
E(T^{\prime})$. Note that $e^{\prime}$ has weight $1$ while $e$ has weight
$0$. Then substituting $e^{\prime}$ with $e$ in $T^{\prime}$ creates a better
MST, a contradiction.

This implies any MST $T^{\prime}$ in $G^{\prime}$ restricted to $G$ is a
spanning tree in $G$. Then, $coverage(F^{\prime},G)\geq k-1$ and thus
$F^{\prime}$ is a $k$-cut in $G$. By our choice of $b^{\prime}$, it follows
that $F^{\prime}$ is an optimal $k$-cut. ∎

######  Corollary 2.

If there exists an $\alpha$-approximation of Budgeted Discrete MMST then there
exists an $\alpha$-approximation of Max Components.
If there exists an $\alpha$-approximation of Targeted Discrete MMST then there
exists an $\alpha$-approximation of $k$-cut.

###### Proof.

It follows from the proof of Theorem 4.1 that given the auxiliary graph
$G^{\prime}$, any feasible solution that spends budget $0\leq b\leq n$ to
upgrade a set $F^{\prime}$ and increases the MST by $T_{b}$ can be transformed
into a feasible solution that spends budget at most $b$, only upgrades
original edges by at most once, does not upgrade any newly added edges and
increases the MST by at least $T_{b}$. Then, it follows that an
$\alpha$-approximation to MMST also produces an $\alpha$-approximation to the
Max Component problem. Similarly, an $\alpha$-approximation to the Targeted
Discrete MMST also provides an $\alpha$ approximation to the Minimum $k$-Cut
Problem.

∎

#### Hardness of Approximation.

Let $G$ be a $d$-regular undirected unweighted graph. The edge expansion
$\phi(S)$ of $S\subset V(G)$ is defined as :

$\phi(S)=\frac{|E(S,V(G)\setminus S)|}{d\min\\{|S|,|V\setminus S|\\}}$

where $E(S,V(G)\setminus S)$ is the set of edges across the partition
$(S,V(G)\setminus S)$.

######  Problem 6 (Small Set Expansion (SSE)).

Given a regular graph $G$, let $\delta,\eta\in(0,1)$. The $SSE(\delta,\eta)$
problem is to distinguish between:

  1. 1.

(Completeness) There exists $S\subset V$ of size $\delta|V|$ such that
$\phi(S)\leq\eta$.

  2. 2.

(Soundness) For every $S\subset V$ of size $\delta|V|$, $\phi(S)\geq 1-\eta$.

The author in [33] showed that assuming SSE is hard given any $\eta$ for some
$\delta$, which is called the SSE hypothesis, or SSEH, $k$-cut is also hard to
approximate to a $2-\varepsilon$ factor. We then provide a similar result for
the Max Component Problem.

######  Theorem 4.2.

Assuming SSEH, it is also hard to approximate Maximum Components to within
$(\frac{1}{2}+\varepsilon)$ factor of the optimum for every constant
$\varepsilon>0$.

###### Proof.

We reduce SSE to Max Components. Given an instance of $SSE(\delta,\eta)$ on a
$d$-regular graph $G$ with sufficiently large $n=|V(G)|$, let $\varepsilon>0$
be a value dependent on $n,\delta$ and $\eta$. We specify later their
relationship. We will show that if $B=(\frac{1}{2}+\eta)\delta dn$, then
solving Maximum Components with approximation ratio
$(\frac{1}{2}+\varepsilon)$ on $G$ with budget $B$ is sufficient to solve this
instance of $SSE$. First, we make the following observations about
Completeness and Soundness.

(Completeness) If there exists $S\subset V$ of size at most $\delta n$ such
that $\phi(S)\leq\eta$, then consider partition the graph into $|S|+1$ groups
where the first group is $V\setminus S$ and each of the remaining groups
contains a single vertex from $S$. The edges between the partitions are those
in $E(S,V\setminus S)$ and the edges within the set $S$. There are
$d|S|\phi(S)\leq\eta d|S|$ edges of the former type and only at most $d|S|/2$
of the latter. Hence, the number of edges between this partition is at most
$(1/2+\eta)d|S|\leq(1/2+\eta)d\delta n$. This implies there exists a
$k^{\prime}$-cut with at most $B$ edges where $k^{\prime}=\delta n+1$.

(Soundness) Suppose that for every $S\subset V$ of size $\delta n$,
$\phi(S)\geq 1-\eta$. Let $k>\delta n(\frac{1}{2}+\frac{\varepsilon}{2})$ and
$T_{1},...,T_{k}\subset V$ be any $k$-partition of the graph. Assume without
loss of generality that $|T_{1}|\leq...\leq|T_{k}|$. Let $A=T_{1}\cup...\cup
T_{i}$ where $i$ is the maximum index such that $|T_{1}\cup...\cup
T_{i}|\leq\delta n$.

We can then add up to $x\delta n$ nodes to $A$, where $(1-x)\delta n$ is the
size of $A$, to obtain a set $A^{\prime}$ of size exactly $\delta n$. Note
that, since $|A^{\prime}|=\delta n$, $\phi(A^{\prime})\geq 1-\eta$, and so
$E(A^{\prime},V\setminus A^{\prime})\geq(1-\eta)d|A^{\prime}|=(1-\eta)d\delta
n$. This implies that $|E(A,V\setminus A)|\geq(1-\eta)d\delta n-x\delta nd$.
We would like to prove that we always have $(1-\eta)d\delta n-x\delta nd\geq
B=(\frac{1}{2}+\eta)\delta dn$. That is, that
$x\leq(1-\eta)-(\frac{1}{2}+\eta)=\frac{1}{2}-2\eta$. Thus we wish to prove
that $|A|\geq(\frac{1}{2}+2\eta)\delta n$.

Suppose for the sake of contradiction that $|A|<(\frac{1}{2}+2\eta)\delta n$.

Since $|A\cup T_{i+1}|>\delta n$, we have $|T_{i+1}|>(\frac{1}{2}-2\eta)\delta
n$. Furthermore, since $A=T_{1}\cup...\cup T_{i}$,
$i\leq|A|<(\frac{1}{2}+2\eta)\delta n$.

Then,

$\begin{split}n&=|T_{1}\cup...\cup T_{k}|\\\ &>|T_{i+1}\cup...\cup
T_{k}|\geq(k-i)\cdot|T_{i+1}|\\\ &>((\frac{1}{2}+\frac{\epsilon}{2})\delta
n-(\frac{1}{2}+2\eta)\delta n)((\frac{1}{2}-2\eta)\delta
n)=(\frac{\epsilon}{2}-2\eta)\delta^{2}n^{2}(\frac{1}{2}-2\eta)\end{split}$

However, if $\eta<\min(\frac{\epsilon}{4},1/4)$, then this is positive and
tends towards infinity as $n$ goes to infinity. Thus for sufficiently large
$n$, this inequality is false, a contradiction. This proves that indeed,
$|A|\geq(\frac{1}{2}+2\eta)\delta n$.

Thus this means that $|E(A,V\setminus A)|\geq B$, which means that any $k$-cut
has at least $B$ edges when $k>\delta n(\frac{1}{2}+\frac{\varepsilon}{2})$.

In other words, if we are in the completeness case, then there exists a $B$
cost cut with $\delta n+1$ components, whereas in the soundness case, all $B$
cost cuts give at most $\delta n(\frac{1}{2}+\frac{\varepsilon}{2})$
components. The gap between the two is more than $\frac{1}{2}+\varepsilon$ and
so an approximation of Maximum Components to within
$(\frac{1}{2}+\varepsilon)$ can distinguish between the two cases. This
concludes the proof. ∎

######  Corollary 3.

Assuming SSEH, Budgeted Discrete MMST is NP-hard to approximate to a
$\frac{1}{2}+\varepsilon$-factor for $\varepsilon>0$.
Assuming SSEH, Targeted Discrete MMST is NP-hard to approximate to a
$2-\varepsilon$-factor for $\varepsilon>0$.

##  5 MST Fortification with all edges starting with the Same Weight

In the previous section, we have shown that the unit MST upgrading problem is
hard even if all the costs are unitary. However, it is unknown if the problem
remains hard if all initial weights start off the same. Thus, consider the
special targeted version of unit MST upgrading where all the initial weights
of the graph start with the same weight. Without loss of generality, assume
the weights all start with $0$. First we provide a polytime algorithm that
solves this problem with a fixed target MST value of $T$. For this section, we
drop the term $G$ and use $coverage(F)$ to denote the coverage of set $F$ in
$G$ with initial weights of zero.

######  Theorem 5.1.

Let $G$ be a graph whose edges have weight $0$ and upgrading costs of $c_{e}$.
Given a fixed target MST value of $T$, there exists an algorithm that runs in
$n^{O(T)}$ time and upgrades edges to produce a final MST value of $T$ while
minimizing the total cost of upgrading.

Note that since all the costs are integral, if it takes budget $B$ to raise
the MST by $T$, then $B\geq T$. Thus, given a bounded constant budget $B$, the
special budgeted version of unit MST upgrading can also be solved exactly in
polytime.

To prove the theorem, we require a supermodular property of coverage.

######  Lemma 4.

(Supermodularity of coverage)

For any $F,F^{\prime}\subseteq E(G)$, $coverage(F)+coverage(F^{\prime})\leq
coverage(F\cup F^{\prime})+coverage(F\cap F^{\prime})$.

###### Proof.

First we decompose our sets by edge weight $F=\cup F_{w_{i}}$ and $F=\cup
F^{\prime}_{w_{i}}$ where $F_{w_{i}}$ and $F^{\prime}_{w_{i}}$ are the set of
edges with weight $w_{i}$ that are also in $F$ and $F^{\prime}$ respectively.
Then

$coverage(F)+coverage(F^{\prime})=coverage(\cup F_{w_{i}})+coverage(\cup
F^{\prime}_{w_{i}})$
$=\sum_{i}(coverage(F_{w_{i}})+coverage(F^{\prime}_{w_{i}}))$

and

$coverage(F\cup F^{\prime})+coverage(F\cap
F^{\prime})=coverage(\cup_{i}(F_{w_{i}}\cup
F^{\prime}_{w_{i}}))+coverage(\cup_{i,j}(F_{w_{i}}\cap F^{\prime}_{w_{j}}))$
$=coverage(\cup_{i}(F_{w_{i}}\cup
F^{\prime}_{w_{i}}))+coverage(\cup_{i}(F_{w_{i}}\cap F^{\prime}_{w_{i}}))$
$=\sum_{i}(coverage(F_{w_{i}}\cup F^{\prime}_{w_{i}})+coverage(F_{w_{i}}\cap
F^{\prime}_{w_{i}}))$

Note that the second equality follows from the fact that $F_{w_{i}}\cap
F^{\prime}_{w_{j}}=\emptyset$ for $i\neq j$. It now suffices to show that for
$F$ and $F^{\prime}$ of a single weight class, the inequality holds.

In consequence, we assume without loss of generality that $F$ and $F^{\prime}$
both contain only edges of weight $w_{i}$. The coverage of any edge-set is the
same as the number of additional components created from its deletion in
$\widetilde{G_{w_{i}}}$. Let $\\{G_{i}\\}_{i=1}^{k}$ be the connected
components of $\widetilde{G_{w_{i}}}\backslash(F\cap F^{\prime})$. Let
$F_{i},F_{i}^{\prime}$ be the set of edges in $G_{i}$ that belongs in
$F,F^{\prime}$ respectively. Let $a_{i},a_{i}^{\prime},b_{i}$ represent the
number of additional components created from $G_{i}$ by deleting
$F_{i},F_{i}^{\prime},F_{i}\cup F_{i}^{\prime}$ respectively. Note that
$a_{i},a_{i}^{\prime},b_{i}$ also represent the coverage of
$F_{i},F_{i}^{\prime},F_{i}\cup F_{i}^{\prime}$ respectively in $G_{i}$. Since
$F_{i}\cap F_{i}^{\prime}=\emptyset$ by construction, it follows that any
spanning tree of $G_{i}$ must contain $a_{i},a_{i}^{\prime}$ edges from
$F_{i},F_{i}^{\prime}$ respectively. Thus $b_{i}\geq a_{i}+a_{i}^{\prime}$. In
$\widetilde{G_{w_{i}}}$, the coverage of $F$ can be viewed as first deleting
$F\cap F^{\prime}$ and then deleting the $F_{i}$’s in sequence and counting
how many additional components it creates. In other words
$coverage(F)=k-1+\sum_{i=1}^{k}a_{i}$. We can obtain similar equations for
$coverage(F^{\prime}),coverage(F\cup F^{\prime})$.

Then,

$\begin{split}coverage(F)&+coverage(F^{\prime})=(k-1+\sum_{i}a_{i})+(k-1+\sum_{i}a_{i}^{\prime})\\\
&\leq(k-1)+(k-1+\sum b_{i})=coverage(F\cap F^{\prime})+coverage(F\cup
F^{\prime})\end{split}$

∎

To prove Theorem 5.1, we also need to solve the following variant of the
knapsack problem:

######  Problem 7 (Unbounded Knapsack Problem).

For $i\in[n]$, let $w_{i}$ and $p_{i}$ be respectively the weight and the
profit of item $i$. Given fixed capacity $W$, find $x_{i}\in\mathbb{Z}_{\geq
0}$ that maximizes $\sum_{i=1}^{n}p_{i}x_{i}$ subject to
$\sum_{i=1}^{n}w_{i}x_{i}\leq W$.

######  Lemma 5.

Given an instance of the Unbounded Knapsack Problem, if each profit $p_{i}$ is
of order $O(n)$, then a solution can be found in time $O(n^{2}p^{2})$ where
$p=\max_{i}p_{i}$.

A solution for this above lemma is proposed in [42]; we formally reproduce the
proof below for completeness.

###### Proof.

Given an instance the Unbounded Knapsack Problem, let $x^{*}$ be an optimal
solution and $P^{*}$ be the optimal profit. Assume without loss of generality
that $p_{1}/w_{1}=\max_{i=1}^{n}\\{p_{i}/w_{i}\\}$. In other words, item $1$
gives the most bang-for-buck. Let $P=\sum_{i=2}^{n}p_{1}p_{i}$. We break into
two cases depending on how $P^{*}$ compares to $P$.

#### Case 1

Suppose $P^{*}\leq P$. Then, consider the following dynamic programming. For
$i\in[n],1\leq p\leq P$, let $f(i,p)$ be the least possible weight of a
solution such that it contains at least one copy of item $i$ and its profit is
exactly $p$. For $i\in[n]$, let $f(i,p_{i})=w_{i}$ and let $f(i,p)=\infty$ for
all $p<p_{i}$. This corresponds to the fact that if a solution contains item
$i$, its profit must be at least $p_{i}$. For $i\in[n],p_{i}<p\leq P$, let
$f(i,p)=\min_{j\in[n]}\\{f(j,p-p_{i})\\}+w_{i}$. Intuitively, this recursion
says that if a solution has profit $p$ and contains item $i$, then removing it
results in a solution with profit $p-p_{i}$ and weight $f(i,p)-w_{i}$. Thus,
searching for the best way to achieve profit $p-p_{i}$ also leads to a
solution for $f(i,p)$. Since $i,p$ are polynomially bounded, all values of $f$
can be computed in polytime. For $1\leq p\leq P$, let
$w(p)=\min_{i\in[n]}\\{f(i,p)\\}$. Then, simply find the largest value of $p$
such that $w(p)\leq W$.

#### Case 2

Suppose $P^{*}>P$. Without loss of generality, assume $x^{*}$ is an optimal
solution that maximizes the value $x^{*}_{1}$. First we claim that
$x^{*}_{1}\neq 0$. Since
$\sum_{i=1}^{n}x_{i}^{*}p_{i}=P^{*}>P=\sum_{i=1}^{n}p_{1}p_{i}$, there exists
$i\in[n]$ such that $x_{i}^{*}\geq p_{1}$. If $i=1$, then we are done.
Otherwise, since $p_{1}/w_{1}\geq p_{i}/w_{i}$, it follows that by swapping
out $p_{1}$ copies of item $i$ and replace it with $p_{i}$ copies of item $1$,
the profit does not change and the weight does not increase. Since $x^{*}$ is
an optimal solution that maximizes $x^{*}_{1}$, it follows that $x^{*}_{1}>0$.

Then, it follows that removing a single copy of item $1$ from $x^{*}$ is an
optimal solution for profit $P^{*}-p_{1}$. Therefore one can recursively
remove $p_{1}$ from $P^{*}$ until the profit falls below $P$ and use the
solutions from Case 1 to build $x^{*}$.

In particular, consider $W^{\prime}$ such that $W-w_{1}<W^{\prime}\leq W$. Let
$w^{\prime}$ be the largest integer such that $W^{\prime}\leq w(P)$ and
$W^{\prime}=W-k^{\prime}w_{1}$ for some integer $k^{\prime}$. Note that
$x^{*}$ has total weight $W^{\prime}$ if and only if there exists $p^{\prime}$
such that $w(p^{\prime})=w^{\prime}$. Then, let $\mathcal{W}$ be the set of
weights $W^{\prime}$ where such $p^{\prime}$ exists for the associated
$w^{\prime}$. Since $x^{*}$ contains a copy of item $1$, its total weight must
be one of the values in $\mathcal{W}$. For each $W^{\prime}\in\mathcal{W}$,
its associated solution must be $x^{\prime}$ and an additional $k^{\prime}$
copies of item $1$. Therefore, its associated profit is
$p^{\prime}+k^{\prime}p_{1}$. Then, taking the solution with the largest
profit $p;+k^{\prime}p_{1}$ is an optimal solution. ∎

###### Proof of Theorem 5.1.

Let $w^{*}$ be an optimal solution representing the final weights of every
edge. Let $b^{*}$ be the upgrading cost to reach the final weights $w^{*}$.
Let $E_{i}^{*}$ represent the set of edges whose final weight is at least $i$.
Then, we can decompose $w^{*}$ into a sequence of lifts where we first lift
$E_{1}^{*}$ by one unit, then $E_{2}^{*}$ and so on. Note that at the time of
lifting $E_{i}^{*}$, the set $E_{i}^{*}$ has the highest weight among all
edges of the graph. Then, it follows from Lemma 1, lifting $E_{i}^{*}$ at time
$i$ increases the MST by exactly the same amount as the coverage of
$E_{i}^{*}$ at the beginning where all weights are the same. Thus, it
motivates us to only look at the coverage of sets at the initial stage where
all weights are $0$.

Define $F_{i}$ to be a set of edges in $G$ with the least upgrading cost such
that $G\backslash F_{i}$ creates $i$ additional components for $i\leq T$. Note
that finding these sets is equivalent to solving $T$ iterations of the Min
$i$-Cut problem, which can be solved in $n^{O(T)}$ time. Let $c(F_{i})$
represent the cost to upgrade the set $F_{i}$ by one unit. It follows that an
optimal solution is a combination of these cuts that maximizes the sum of the
coverage while ensuring the cost is within budget.

Then, consider the following instance of the Unbounded Knapsack Problem.
Consider $T$ items $F_{1},...,F_{T}$ where $F_{i}$ has weight $c(F_{i})$ and
profit $i$. It follows from Lemma 5 that a solution can be obtained in
polynomial time.

Let $x^{*}$ be an optimal solution to the knapsack problem. Now, we slightly
modify the knapsack solution so that the subsets form a chain. Suppose there
exists $i,j$ where neither $F_{i},F_{j}$ are subsets of the other one and
their $x^{*}$ values are non-zero. Then, by Lemma 4, we can use $F_{i}\cap
F_{j},F_{i}\cup F_{j}$ instead since it does not change the total upgrading
cost. Then, we can perform these uncrossing operations to obtain a family of
edge-sets $F_{k}^{*}$ and integers $y_{k}^{*}$ such that
$\sum_{k}y_{k}^{*}coverage(F_{k}^{*})\geq\sum_{i}x_{i}^{*}coverage(F_{i})$. It
is worth mentioning that since there are at most $T$ edge-sets with non-zero
$x^{*},y^{*}$ values, it takes at most $T^{2}$ many applications of Lemma 4 to
obtain the sets $F_{k}^{*}$. Since $F_{k}^{*}$ forms a chain, we can lift them
in sequence from the largest to the smallest by $y_{k}^{*}$ amount at a time.
It follows from Lemma 1 that every lift increases the MST by exactly
$coverage(F_{k}^{*})$. Thus, it follows that this process reaches target $T$
and minimizes the downgrading cost. ∎

######  Corollary 4.

For every constant $\varepsilon>0$, there exists a
$(1/2-\varepsilon)$-approximation algorithm for MMST with uniform starting
weights.

###### Proof.

Let us fix $\varepsilon>0$. We now describe an algorithm that runs in
polynomial time and that gives a $(1/2-\varepsilon)$-approximation algorithm
for MMST with uniform starting weights. Let $(G,0,c,B)$ be an instance of MMST
with 0 weight for all edges. Let $opt$ be the optimal increase for the MST in
an optimal solution. We first run the greedy algorithm in Theorem 3.2 in
polynomial time, giving us a $t$ increase in the MST weight, with $opt\geq
t\geq\frac{opt}{2}-1$. If $t\geq\frac{1}{\varepsilon}$, then
$opt\geq\frac{1}{\varepsilon}$ and so $t\geq
opt(\frac{1}{2}-\frac{1}{opt})\geq opt(\frac{1}{2}-\varepsilon)$. If
$t<\frac{1}{\varepsilon}$, then $\frac{1}{\varepsilon}>\frac{opt}{2}-1$, and
$opt<2+\frac{2}{\varepsilon}$ and so since $\varepsilon$ is fixed, by Theorem
5.1, an optimal solution can be obtained in this case in time
$n^{O(2+2/\varepsilon)}$ which is polynomial in $n$ for any fixed constant
$\varepsilon$.

Thus, in all cases, the algorithm runs in polynomial time and finds a
$(1/2-\varepsilon)$-approximation. ∎

##  6 Extension and Open Problem

We expect our modifications to work in a straightforward manner for the
extension of the main problems from MSTs (graphical matroid bases) to general
matroid bases following the framework in [13]. The main open problem from our
work is to extend it to the case of directed graphs.

## References

  * [1] Ahuja RK, Orlin JB. A capacity scaling algorithm for the constrained maximum flow problem. Networks 25(2), 89-98 (1995)
  * [2] André Linhares, C.SF. Improved algorithms for mst and metric-tsp interdiction. Proceedings of 44th International CoFlloquium on Automata, Languages, and Programming (ICALP) 32, 1–14 (2017)
  * [3] M. 0. Ball, B. L. Golden, and R. V. Vohra. Finding the most vital arcs in a network. Oper. Res. Lett., 8:73-76, 1989.
  * [4] Burch, C., Carr, R., Krumke, S., Marathe, M., Phillips, C., Sundberg, E. A decomposition-based pseudoapproximation algorithm for network flow inhibition. In: L., W.D. (ed.) Network Interdiction and Stochastic Integer Programming, vol. 26, pp. 51–68. springer (2003)
  * [5] Aissi, Hassene, Da Qi Chen, and R. Ravi.  Downgrading to Minimize Connectivity.  arXiv preprint arXiv:1911.11229 (2019).
  * [6] Bar-Noy, Amotz, Samir Khuller, and Baruch Schieber. The complexity of finding most vital arcs and nodes. Technical report, College Park, MD, USA (1998).
  * [7] Chestnut, S.R., Zenklusen, R. Interdicting structured combinatorial optimization problems with $\\{$0, 1$\\}$-objectives. Mathematics of Operations Research 42(1), 144–166 (2016)
  * [8] Chestnut, S.R., Zenklusen, R. Hardness and approximation for network flow interdiction. Networks 69(4), 378–387 (2017)
  * [9] Cunningham W.H. Optimal attack and reinforcement of a network. J. ACM 32, 3 (July 1985), 549–561. (1985)
  * [10] Ford, L. R., Jr., Fulkerson, D. R. Flows in networks. Princeton University Press xii+194 pp. (1962)
  * [11] Dinitz, M., Gupta, A.  Packing interdiction and partial covering problems.  International Conference on Integer Programming and Combinatorial Optimization (IPCO), 157-168, 2013.
  * [12] Frederickson, Greg N., and Roberto Solis-Oba. Increasing the weight of minimum spanning trees. Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms (SODA). 1996.
  * [13] Frederickson, Greg N., and Roberto Solis-Oba.  Algorithms for measuring perturbability in matroid optimization.  Combinatorica 18(4), 503-518 (1998).
  * [14] Frederickson, Greg N., and Roberto Solis-Oba. Increasing the weight of minimum spanning trees. J. Algorithms 33, 244–266. 1999.
  * [15] Fulkerson, D. R., Harding, G. C.  Maximizing the minimum source-sink path subject to a budget constraint.  Mathematical Programming, 13(1), 116-118 (1977).
  * [16] Fulkerson, D. R.  Increasing the Capacity of a Network: The Parametric Budget Problem.  Management Science 5, 4, 472-483 (1959).
  * [17] Golden, B. A problem in network interdiction. Naval Research Logistics Quarterly 25(4), 711–713 (1978)
  * [18] Grötschel, M., Monma, C. L., Stoer, M.  Design of survivable networks.  Handbooks in operations research and management science, 7, 617-672 (1999).
  * [19] L. Hsu, R. Jan, Y. Lee, and C. Hung.  Finding the most vital edge with respect to minimum spanning tree in weighted graphs.  Information Processing Letters 39:277-281 1991.
  * [20] L. Hsu, P. Wang, arid C. Wu.  Parallel algorithms for finding the most vital edge with respect to minimum spanning tree.  Parallel Computing 18:1143-1155, 1992.
  * [21] Harris, T.E., Ross, F.S. Fundamentals of a method for evaluating rail net capacities. Tech. rep., Santa Monica, California (1955)
  * [22] Israeli, E., Wood, R.K. Shortest-path network interdiction. Networks 40(2), 97–111 (2002)
  * [23] K. Iwano and N. Katoh. Efficient algorithms for finding the most vital edge of a minimum spanning tree. Information Processing Letters 48:211-213, 1993.
  * [24] Alpár Jüttner. On Budgeted Optimization Problems. SIAM J. Discrete Math., 20(4), 880–892 (2006).
  * [25] Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V., Rudolf, G., Zhao, J.  On short paths interdiction problems: Total and node-wise limited interdiction.  Theory of Computing Systems, 43(2), 204-233 (2008).
  * [26] Krumke, S. O., Marathe, M. V., Noltemeier, H., Ravi, R., and Ravi, S. S. Approximation algorithms for certain network improvement problems. Journal of Combinatorial Optimization, 2(3), 257-288.
  * [27] Sven Oliver Krumke, Madhav V. Marathe, Hartmut Noltemeier, R. Ravi, S. S. Ravi, Ravi Sundaram, and Hans-Christoph Wirth.  Improving Minimum Cost Spanning Trees by Upgrading Nodes,  J. Algorithms 33(1): 92-111 (1999).
  * [28] K. Liri and M. Chern. The most vital edges in the minimum spanning tree problem. Information Processing Letters 45:25-31, 1993.
  * [29] Sven Oliver Krumke, Hartmut Noltemeier, Madhav V. Marathe, R. Ravi, S. S. Ravi, Ravi Sundaram, and Hans-Christoph Wirth.  Improving Spanning Trees by Upgrading Nodes.  Theor. Comput. Sci. 221(1-2): 139-155 (1999).
  * [30] Lap Chi Lau, R. Ravi and Mohit Singh.  Iterative Methods in Combinatorial Optimization. Cambridge University Press, 2011.
  * [31] Magnouche, Y., Martin, S.  Most vital vertices for the shortest s–t path problem: complexity and Branch-and-Cut algorithm.  Optimization Letters, 1-15 (2020).
  * [32] K. Malik, A. K. Mittal, and S. K. Gupta. The k most vital arcs in the shortest path problem. Operations Research Letters 8:223-227, 1989.
  * [33] Manurangsi, P.  Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis.  Algorithms 11.1 : 10 (2018).
  * [34] Phillips, C.A. The network inhibition problem. STOC (1993)
  * [35] R. Ravi and Amitabh Sinha.  Approximating k-cuts via network strength.  SODA 2002: 621-622.
  * [36] Schrijver, A. On the history of the transportation and maximum flow problems. Mathematical Programming 91(3), 437–445 (2002)
  * [37] Stoer, M. Design of survivable networks. Springer (2006).
  * [38] Éva Tardos. A strongly polynomial minimum cost circulation algorithm. Combinatorica volume 5, 247–255 (1985).
  * [39] R. E. Tarjan. Sensitivity analysis of minimum spanning trees and shortest path trees. Information Processing Letters, 14:30-33 1982.
  * [40] Thorup, M. Minimum k-way cuts via deterministic greedy tree packing. Proceedings of the fortieth annual ACM symposium on Theory of computing (STOC ’08), 159–166. (2008)
  * [41] Wood, R. Deterministic network interdiction. Mathematical and Computer Modeling 17(2), 1–18 (1993)
  * [42] Young, Y. Is the knapsack variant with small profit and unlimited repetition of items NP-hard?. Theoretical Computer Science Stack Exchange https://cstheory.stackexchange.com/q/47443
  * [43] Zenklusen, R. Matching interdiction. Discrete Applied Mathematics 145(15) (2010)
  * [44] Zenklusen, R. Network flow interdiction on planar graphs. Discrete Applied Mathematics 158(13) (2010)
  * [45] Zenklusen, R. Connectivity interdiction. Operations Research Letters 42(67), 450–454 (2014)
  * [46] Zenklusen, R. An O(1) approximation for minimum spanning tree interdiction. Proceedings of 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 709–728 (2015)