1 Introduction

For problems of security or reliability, it is important to assess the capacity of a system to resist to a destruction or a failure of a number of its entities. This amounts to identifying critical entities which can be determined with respect to a measure of performance or a cost associated to the system. Modeling the network as a weighted connected graph where entities are edges or nodes and costs are weights associated to edges, one way of identifying critical entities is to determine a subset of edges or nodes whose removal from the graph causes the largest cost increase. Another way is to find a subset of edges or nodes of minimum cardinality whose removal involves that the optimal cost in the residual network is larger than a given threshold. In the literature these problems are referred to respectively as the k most vital edges/nodes problem and min edge/node blocker problem. In this paper the k most vital edges/nodes and min edge/node blocker versions for the minimum spanning tree problem are investigated.

The problem of finding the k most vital edges of a graph has been studied for various problems including shortest path (Bar-Noy et al. 1995; Khachiyan et al. 2008; Nardelli et al. 2001), maximum flow (Wollmer 1964; Ratliff et al. 1975; Wood 1993), 1-median and 1-center (Bazgan et al. 2010). For the minimum spanning tree problem, Frederickson and Solis-Oba (1996) showed that k Most Vital Edges MST is NP-hard and proposed an O(logk)-approximation algorithm. For a fixed k, the problem is obviously polynomial. The case k=1 has been largely studied in the literature (Hsu et al. 1991; Iwano and Katoh 1993; Suraweera et al. 1995). Several exact algorithms based on an explicit enumeration of possible solutions have been proposed (Liang 2001; Liang and Shen 1997; Shen 1999; Bazgan et al. 2011).

After introducing some preliminaries in Sect. 2, we show in Sect. 3 that k Most Vital Edges MST is NP-hard even for complete graphs with weights 0 or 1 and 3-approximable for graphs with weights 0 or 1. We also prove, in Sect. 4, that k Most Vital Nodes MST is not approximable within a factor n 1−ϵ, for any ϵ>0, unless NP=ZPP, even for complete graphs of order n with weights 0 or 1. In Sect. 5, we establish that Min Edge Blocker MST is NP-hard even for complete graphs with weights 0 or 1. In Sect. 6, we show that Min Node Blocker MST is NP-hard to approximate within a factor 1.36 even for graphs with weights 0 or 1. Final remarks are provided in Sect. 7.

2 Basic concepts and preliminary results

Let G=(V,E) be a weighted undirected connected graph where |V|=n, |E|=m and w(e)≥0 is the integer weight of each edge e∈E. Denote by G−R the graph obtained from G by removing the subset R of edges or nodes.

We consider in this paper the k most vital edges (nodes) and min edge (node) blocker versions of the minimum spanning tree problem. These problems are defined as follows:

k Most Vital Edges (resp. Node) MST

Input: :

A connected weighted graph G=(V,E) where each edge e∈E has an integer weight w e ≥0 and a positive integer k.

Output: :

A subset S ∗⊆E (resp. S ∗⊆V), with |S ∗|=k, such that the weight of a minimum spanning tree in G−S ∗ is maximum.

For an instance of k Most Vital Edges MST defined on a graph G, we consider that k≤λ(G)−1 where λ(G) is the edge-connectivity of G. Otherwise, any selection of k edges including the edges of a minimum cardinality cut would lead to a solution with infinite value since we disconnect G.

For an instance of k Most Vital Nodes MST defined on a graph G, we consider that k≤κ(G)−1, where κ(G) is the node-connectivity of G. Otherwise, any selection of k nodes including the nodes of a minimum node separator would lead to a solution with infinite value since we disconnect G.

Min Edge (resp. Node) Blocker MST

Input: :

A connected weighted graph G=(V,E) where each edge e∈E has an integer weight w e ≥0 and a positive integer U.

Output: :

A subset S ∗⊆E (resp. S ∗⊆V) of minimum cardinality such that the weight of a minimum spanning tree in G−S ∗ is greater than or equal to U.

An optimal solution S ∗ of an instance of Min Edge (resp. Node) Blocker MST defined on a graph G is such that |S ∗|≤λ(G) (resp. |S ∗|≤κ(G)) since, at worst, it is necessary to disconnect G so as to exceed the threshold U.

Given an optimization problem in NPO and an instance I of this problem, we use |I| to denote the size of I, opt(I) to denote the optimum value of I, and val(I,S) to denote the value of a feasible solution S of instance I. The performance ratio of S (or approximation factor) is \(r(I,S)=\max\{\frac{\mathit{val}(I,S)}{\mathit{opt}(I)},\frac{\mathit{opt}(I)}{\mathit{val}(I,S)}\}\). The error of S, ε(I,S), is defined by ε(I,S)=r(I,S)−1.

For a function f, an algorithm is an f(|I|)-approximation, if for every instance I of the problem, it returns a solution S such that r(I,S)≤f(|I|).

The notion of a gap-reduction was introduced in Arora and Lund (1996). A maximization problem Π is called gap-reducible to a maximization problem Π′ with parameters (c,ρ) and (c′,ρ′), ρ,ρ′≥1, if there exists a polynomial time computable function f which maps any instance I of Π to an instance I′ of Π′, while satisfying the following properties.

  • If opt(I)≥c then opt(I′)≥c′

  • If \(\mathit{opt}(I) < \frac{c}{\rho}\) then \(\mathit{opt}(I^{\prime}) <\frac{c^{\prime}}{\rho^{\prime}}\).

The interest of a gap-reduction is that if Π is not approximable within a factor ρ then Π′ is not approximable within a factor ρ′.

The notion of an E-reduction (error-preserving reduction) was introduced by Khanna et al. (1994). A problem Π is called E-reducible to a problem Π′, if there exist polynomial time computable functions f, g and a constant β such that

  • f maps an instance I of Π to an instance I′ of Π′ such that opt(I) and opt(I′) are related by a polynomial factor, i.e. there exists a polynomial p such that opt(I′)≤p(|I|)opt(I),

  • g maps any solution S′ of I′ to one solution S of I such that ε(I,S)≤βε(I′,S′).

An important property of an E-reduction is that it can be applied uniformly to all levels of approximability; that is, if Π is E-reducible to Π′ and Π′ belongs to \(\mathcal{C}\) then Π belongs to \(\mathcal{C}\) as well, where \(\mathcal{C}\) is a class of optimization problems with any kind of approximation guarantee (see also Khanna et al. 1994).

A problem Π is called E-equivalent to a problem Π′ if Π is E-reducible to Π′ and Π′ is E-reducible to Π.

3 k most vital edges MST

Frederickson and Solis-Oba (1996) show that k Most Vital Edges MST is NP-hard even for graphs with weights 0 or 1 and that the problem is O(logk)-approximable for graphs with arbitrary weights. In this section, we strengthen the NP-hardness result of Frederickson and Solis-Oba by specifying a more restricted class of instances for which the problem remains NP-hard. Moreover, we establish a constant approximation result for graphs with weights 0 or 1.

First we show that we can decide in polynomial time if the optimum value is a fixed constant.

Proposition 1

For any fixed value c≥0, it can be checked in polynomial time if the optimum value of k Most Vital Edges MST on graphs with weights 0 or 1 on edges is c.

Proof

Consider an instance I of k Most Vital Edges MST formed by a weighted graph G=(V,E), with weights 0 or 1, and by a positive integer k. Denote by G 0=(V,E 0) the subgraph induced by the edges of weight 0. Let E 1=E∖E 0 and m 1=|E 1|.

We have that opt(I)=0 if and only if G 0 is (k+1) edge-connected. Indeed, if opt(I)=0 then G 0 must be (k+1) edge-connected otherwise opt(I)>0. Conversely, if G 0 is (k+1) edge-connected, then removing any subset of k edges from G 0 induces a minimum spanning tree of weight 0. Consequently, it is polynomial to verify if opt(I)=0 since it is polynomial to determine the edge-connectivity of a given graph. Once we checked iteratively that opt(I)≠ℓ, for 0≤ℓ≤c−1, we consider all the \(\binom{m_{1}}{c} \) graphs G 0∪R, for any subset R⊆E 1 with |R|=c. We can decide in polynomial time if opt(I)=c by verifying if G 0∪R is (k+1) edge-connected. □

We show in the following that k Most Vital Edges MST is E-equivalent to Max Component defined as follows.

Max Component

Input::

a connected graph and a positive integer k.

Output::

a subset of k edges to be removed such that the number of connected components in the obtained graph is maximum.

Theorem 1

k Most Vital Edges MST for graphs with weights 0 or 1 is E-equivalent to Max Component.

Proof

We first show that Max component is E-reducible to k Most Vital Edges MST. Given an instance I of Max component formed by a graph G=(V,E) with n nodes, we construct an instance I′ of k Most Vital Edges MST consisting of a complete graph G′=(V,E′) where each edge (i,j)∈E′ is assigned a weight 0 if (i,j)∈E and 1 otherwise.

Let S ∗⊆E be a subset of k edges whose deletion from G generates a maximum number of connected components. By removing S ∗ from G′, all the connected components of G−S ∗ are linked in G′−S ∗ by edges of weight 1. Thus, the weight of a minimum spanning tree in G′−S ∗ is equal to the number of connected components in G−S ∗ minus 1. Therefore, we have opt(I′)≥opt(I)−1.

Let S′⊆E′ be a subset of k edges whose deletion from G′ generates a minimum spanning tree in G′−S′ of weight v. If S′ contains edges of weight 1 then by replacing these edges by edges of weight 0, either the weight of a minimum spanning tree in the modified graph remains unchanged or it increases. Thus, considering S defined from S′ by replacing edges of weight 1 with edges from E′∖S′ of weight 0, se define a subset S⊆E such that G−S contains at least v+1 connected components. Hence, val(I,S)≥val(I′,S′)+1. In particular, when S is an optimum solution, we have opt(I′)+1≤val(I,S)≤opt(I). It follows from the previous result that opt(I)=opt(I′)+1.

Therefore, we have opt(I′)≤opt(I) and \(\varepsilon (I,S)=\frac{\mathit{opt}(I)}{\mathit{val}(I,S)}-1\leq\frac{\mathit{opt}(I^{\prime})+1}{\mathit{val}(I^{\prime},S')+1}-1=\frac{\mathit{opt}(I^{\prime})-\mathit{val}(I^{\prime},S')}{\mathit{val}(I^{\prime},S')+1}\leq\frac{\mathit{opt}(I^{\prime})-\mathit{val}(I^{\prime},S')}{\mathit{val}(I^{\prime},S')}=\varepsilon (I^{\prime},S')\).

We show now that k Most Vital Edges MST is E-reducible to Max component. Consider an instance I of k Most Vital Edges MST formed by a graph G=(V,E) with edges of weight 0 or 1. From Proposition 1, we can consider that opt(I)>0. We construct an instance I′ of Max component consisting of the graph G′=(V,E′) obtained from G by considering only edges of weight 0.

Let S ∗ be a subset of k edges whose removal from G generates a minimum spanning tree T in G−S ∗ of maximum weight. The weight of T being equal to the number of edges of T of weight 1, by deleting edges of S ∗∩E′ plus any k−|S ∗∩E′| edges from E′, the number of connected components in G′−S ∗ is at least equal to the weight of T plus 1. Thus, we have opt(I′)≥opt(I)+1.

Consider a subset S′ of k edges whose deletion from G′ partitions G′ into val(I′,S′) connected components. If val(I′,S′)=1 then we can replace S′ by another solution with value at least 2 obtained by selecting k edges including a minimum cut since from Proposition 1, G′ is not (k+1) edge-connected. Thus, we can assume that val(I′,S′)≥2. By removing S′ from G, all connected components of G′−S′ are linked in G−S′ by edges of weight 1. Thus, the weight of a minimum spanning tree in G−S′ is equal to val(I′,S′)−1. Then, val(I,S′)≥val(I′,S′)−1. In particular, when S′ is an optimum solution in G′, we have val(I,S′)=opt(I′)−1 and thus opt(I)≥opt(I′)−1. It follows from the previous result that opt(I′)=opt(I)+1.

Therefore, since opt(I)>0, we have opt(I′)≤2opt(I) and \(\varepsilon (I,S')= \frac{\mathit{opt}(I)}{\mathit{val}(I,S')}-1\leq\frac {\mathit{opt}(I^{\prime})-1}{\mathit{val}(I^{\prime},S')-1}-1\) \(=\frac{\mathit{opt}(I^{\prime})-\mathit{val}(I^{\prime},S')}{\mathit{val}(I^{\prime},S')-1}=\frac {\mathit{val}(I^{\prime},S')}{\mathit{val}(I^{\prime},S')-1}\frac{\mathit{opt}(I^{\prime})-\mathit{val}(I^{\prime},S')}{\mathit{val}(I^{\prime},S')}\leq2\frac{\mathit{opt}(I^{\prime})-\mathit{val}(I^{\prime},S')}{\mathit{val}(I^{\prime},S')}=2\varepsilon (I^{\prime},S')\). □

From Theorem 1, we obtain the two following results. First, we slightly strengthen the NP-hardness result of Frederickson and Solis-Oba (1996) by specifying a more restricted class of instances for which the problem remains NP-hard.

Corollary 1

k Most Vital Edges MST is NP-hard even for complete graphs with weights 0 or 1.

Proof

The E-reduction from Max Component to k Most Vital Edges MST constructs from any graph G a complete graph G′ with weights 0 or 1. Since Max Component is NP-hard (Frederickson and Solis-Oba 1996), the results follows. □

Second, we establish a constant approximation result for graphs with weights 0 or 1.

Corollary 2

k Most Vital Edges MST is 3-approximable for graphs with weights 0 or 1.

Proof

In the E-reduction from k Most Vital Edges MST to Max component, we have shown that any solution S of I′ is such that ε(I,S)≤2ε(I′,S). Thus, r(I,S)−1≤2(r(I′,S)−1) and then r(I,S)≤2r(I′,S)−1. Since r(I′,S)=2 as established in Frederickson and Solis-Oba (1996), we have r(I,S)≤3. □

4 k most vital nodes MST

We study in this section the complexity of k Most Vital Nodes MST. First we show that k Most Vital Nodes MST is at least as hard as k Most Vital Edges MST by establishing an E-reduction from the edge version to the node version. As far as we know, this is the first result in the literature that establishes a direct relationship between the k most vital edge version and the k most vital node version of a problem. Using the NP-hardness of the edge version even for graphs with weights 0 or 1 (Frederickson and Solis-Oba 1996), this reduction implies the NP-hardness of k Most Vital Nodes MST on the same class of graphs. We strengthen this result by proving that k Most Vital Nodes MST is not approximable within a factor n 1−ϵ, for any ϵ>0, if NP≠ZPP, even for complete graphs with weights 0 or 1.

Theorem 2

k Most Vital Edges MST is E-reducible to k Most Vital Nodes MST.

Proof

Consider an instance I of k Most Vital Edges MST formed by a weighted graph G=(V,E) with V={v 1,…,v n } and |E|=m. We construct an instance I′ of k Most Vital Nodes MST formed by a graph G′=(V′,E′) as follows (see Fig. 1). We consider in G′ the nodes of V and m nodes r 1,…,r m . Let R={r 1,…,r m }. To each edge e ℓ =(v i ,v j )∈E of weight w ij , ℓ=1,…,m and i<j, we associate two edges in E′ : (v i ,r ℓ ) of weight w ij and (r ℓ ,v j ) of weight 0. Let \(K_{k}^{v_{i}}\), for i=1,…,n, be n complete graphs of size k with \(X_{v_{i}}=\{v_{i}^{1},\ldots,v_{i}^{k}\}\) and weights 0 on their edges. We connect each node v i , for i=1,…,n, to the k nodes of \(K_{k}^{v_{i}}\) and assign a weight 0 to these added edges. We also add, for each edge (v i ,r ℓ )∈E′ the edges \((v_{i}^{h},r_{\ell})\), for h=1,…,k, with the same weight as the weight of the edge (v i ,r ℓ ).

Fig. 1
figure 1

Construction of an instance of k Most Vital Nodes MST from an instance of k Most Vital Edges MST

Full size image

Suppose first that there exists a subset S ∗⊆E, with |S ∗|=k, such that a minimum spanning tree T in G−S ∗ has a maximum weight. We set N ∗={r ℓ :e ℓ ∈S ∗}. By deleting N ∗ from G′, we construct a spanning tree T′ in G′−N ∗ as follows: we take for each edge e ℓ =(v i ,v j )∈T with i<j, the edges (v i ,r ℓ ) and (r ℓ ,v j ) in T′, for each edge \(e_{h}=(v_{i},v_{j}) \not\in T\) with i<j, the edge (r h ,v j ) in T′, and we add the paths \(v_{i},v_{i}^{1},\ldots,v_{i}^{k}\), i=1,…,n. We prove, by contradiction, that T′ is a minimum spanning tree in G′−N ∗. Suppose that there exists a spanning tree T″ in G′−N ∗ of weight strictly inferior to that of T′. Then, the spanning tree constituted by the edges e ℓ =(v i ,v j ) such that (v i ,r ℓ )∈T″ has a smaller weight than T in G−S ∗, contradicting the optimality of T. Thus, T′ is a minimum spanning tree in G′−N ∗. Therefore, we have opt(I′)≥opt(I).

Consider now a subset N, with |N|=k, and a minimum spanning tree T′ in G′−N. If N contains v i or one node \(v_{i}^{h}\), for a given i and h, then the weight of a MST in G′−N is the same as in G′−(N∖{v i }) or \(G'-(N\setminus \{v_{i}^{h}\})\). When removing all nodes \(v_{i}, v_{i}^{h}\) from N we obtain a subset N′⊆R, |N′|≤k. Since N′ corresponds to edges in G, any subset N″⊆R containing N′ such that |N″|=k is such that the weight of a MST in G′−N″ is at least as large as the weight of a MST in G′−N′. Let S={e ℓ :r ℓ ∈N″}. Consider T the spanning tree in G−S constituted by the edges e ℓ =(v i ,v j ) such that the edge (v i ,r ℓ )∈T′. T is optimal, since otherwise, the existence of a spanning tree T″ of weight strictly inferior to that of T would imply that the corresponding spanning tree constructed from T″ in G′−N″, as explained above, has a weight strictly inferior to that of T′. Thus, T is a minimum spanning tree in G−S of the same weight as T′. Hence, val(I,S)=val(I′,N″). In particular, when N″ is an optimal solution in G′, we have opt(I′)=val(I,S)≤opt(I). It follows from the previous result that opt(I)=opt(I′). Therefore, we have ε(I,S)=ε(I′,N″). □

Theorem 3

k Most Vital Nodes MST is not approximable within a factor n 1−ϵ, for any ϵ>0, unless NP=ZPP, even for complete graphs of order n with weights 0 or 1.

Proof

We propose a gap-reduction from Max independent set to k Most Vital Nodes MST.

Denote by α(G) the cardinality of maximum independent set of G. Let g be the non approximation gap of Max independent set. Thus, for a given integer ℓ, it is NP-hard to decide if α(G)=ℓ or \(\alpha(G) <\frac{\ell}{g}\).

Given an instance I of Max independent set formed by a graph G=(V,E), we construct an instance I′ of k Most Vital Nodes MST constituted by a complete graph G′=(V,E′) where each edge (i,j)∈E′ is assigned a weight 0 if (i,j)∈E and 1 otherwise (see Fig. 2). We set k=n−ℓ. We show that:

  1. 1.

    α(G)=ℓ⇒opt(I′)≥ℓ−1

  2. 2.

    \(\alpha(G)< \frac{\ell}{g} \Rightarrow \mathit{opt}(I^{\prime})<\frac{\ell-1}{g}\).

Fig. 2
figure 2

Construction of an instance of k Most Vital Nodes MST from an instance of Max Independent Set

Full size image

1. Suppose first that there exists an independent set V ∗ in G of cardinality ℓ and let N ∗=V\V ∗. By removing N ∗ from G′, all nodes of G′−N ∗ are connected by edges of weight 1 only. Thus, we obtain a minimum spanning tree in G′−N ∗ of value ℓ−1. Therefore, opt(I′)≥ℓ−1.

2. Suppose now that \(\alpha(G) < \frac{\ell}{g}\). Hence, there exists a maximum independent set V ∗ such that \(|V^{*}| < \frac{\ell}{g}\). If the node set N ∗ of cardinality n−ℓ to be removed from G′ is such that N ∗∩V ∗=∅ then let V 1=V\(N ∗∪V ∗). Each node of V 1 is at least connected to one node of V ∗ by an edge of weight 0, otherwise V ∗∪{v} would be an independent set in G of larger cardinality. Thus, the weight of a minimum spanning tree in G′−N ∗ cannot exceed \(\frac{\ell}{g}-1\). Since g>1, we have \(\frac{\ell}{g}-1 < \frac{\ell-1}{g}\). Therefore if \(\alpha(G)< \frac{\ell}{g} \) then \(opt(I^{\prime}) <\frac{\ell-1}{g}\). If N ∗∩V ∗≠∅ then a minimum spanning tree in G′−N ∗ would have a weight strictly inferior to \(\frac{\ell}{g}-1\).

Since Max independent set is not approximable within a factor n 1−ϵ, for any ϵ>0, unless NP=ZPP (Håstad 1999), we deduce that k Most Vital Nodes MST is also not n 1−ϵ-approximable, for any ϵ>0, unless NP=ZPP. □

From Theorem 3 and Corollary 2, we can give the following result.

Corollary 3

There is no E-reduction from k Most Vital Nodes MST for graphs with weights 0 or 1 to k Most Vital Edges MST for graphs with weights 0 or 1.

5 Min edge blocker MST

We present in the following a relationship between k Most Vital Edges MST and Min Edge Blocker MST.

Proposition 2

k Most Vital Edges MST and Min Edge Blocker MST are polynomial-time equivalent.

Proof

If an algorithm \(\mathcal{A}_{k}\) solves k Most Vital Edges MST defined on graph G for all 1≤k≤λ(G)−1, then we can run \(\mathcal{A}_{k}\) for k=1,…,λ(G)−1 and choose the smallest k yielding optimum at least U. If no k exists then the optimum for Min Edge Blocker MST is λ(G). Conversely, if an algorithm \(\mathcal{B}_{U}\) solves Min Edge Blocker MST with any bound U, we can apply binary search to locate the largest U that requires the removal of at most k nodes. □

Theorem 4

Min Edge Blocker MST is NP-hard even for complete graphs with weights 0 or 1.

Proof

Follows from Proposition 2 and Corollary 1. □

6 Min node blocker MST

The equivalent of Proposition 2 applied to nodes also holds (with a similar proof).

Proposition 3

k Most Vital Nodes MST and Min Node Blocker MST are polynomial-time equivalent.

Theorem 5

Min Node Blocker MST is NP-hard even for complete graphs with weights 0 or 1.

Proof

Follows from Proposition 3 and Theorem 3. □

This result could also be established by the following gap-reduction from Min Edge Blocker MST.

Theorem 6

Min Edge Blocker MST is gap-reducible to Min Node Blocker MST.

Proof

Consider an instance I for Min Edge Blocker MST formed by a graph G=(V,E), with |V|=n and |E|=m, and a positive integer U. We construct an instance I′ for Min Node Blocker MST, constituted by a graph G′=(V′,E′) and a positive integer U, using the same construction as in Theorem 2, but we modify the size of the n complete graphs which we set to be m+1. We show that

  1. 1.

    opt(I)≤c⇒opt(I′)≤c

  2. 2.

    opt(I)>cρ⇒opt(I′)>cρ.

1. Let S ∗⊆E be a subset of minimum cardinality such that a minimum spanning tree T in G−S ∗ has a weight at least U. We set N ∗={r ℓ :e ℓ ∈S ∗}. By deleting N ∗ from G′, we construct a minimum spanning tree T′ in G′−N ∗ of the same weight as that of T as explained in Theorem 2. Thus, the weight of T′ is at least U. Therefore, opt(I′)≤opt(I)≤c.

2. Suppose now that opt(I)>cρ. When we remove all nodes of R from G′, the weight of a minimum spanning tree is infinite. Hence, opt(I′)≤m. Let N⊆V′ be an optimal solution whose deletion generates a minimum spanning tree T′ in G′−N of weight at least U. If N contains v i or one node \(v_{i}^{h}\), for a given i and h, then N must contain all the m+1 nodes v i and \(X_{v_{i}}\), since otherwise the weight of a minimum spanning in G′−N is the same as in G′−(N∖{v i }) or \(G'-(N\setminus\{v_{i}^{h}\})\). Therefore, since opt(I′)≤m, we can consider that N⊆R. Let S={e ℓ :r ℓ ∈N}. We construct a minimum spanning tree T in G−S as explained in Theorem 2. The weight of T being equal to the weight of T′ is at least U. Hence, opt(I)≤val(I,S)=val(I′,N)=opt(I′) and thus opt(I′)>cρ. □

In the absence of known inapproximability results for Min Edge Blocker MST, we can only exploit the above gap-reduction to establish the NP-hardness of Min Node Blocker MST. Nevertheless, we can obtain the following stronger result.

Theorem 7

Min Node Blocker MST is NP-hard to approximate within a factor 1.36 even for graphs with weights 0 or 1.

Proof

We propose a gap-reduction from Min Vertex Cover. Consider an instance I of Min Vertex Cover formed by a graph G=(V,E) with V={v 1,…,v n }. We construct from I, an instance I′ of Min Node Blocker MST constituted by a graph G′=(V′,E′) and a positive integer U as follows (see Fig. 3). G′ is a copy of G to which we add a path x 1,x 2,…,x n with X={x 1,…,x n } and we connect each node x i to the nodes \(x_{i}^{1},\ldots,x_{i}^{n}\) of a complete graph \(K_{n}^{i}\) of size n. We also connect each node \(x_{i}^{r}\) to node x i+1 and each node x i to node \(x_{i+1}^{r}\) for i=1,…,n−1 and r=1,…,n. We connect each node v i to nodes x i and \(x_{i}^{r}\), for i=1,…,n and r=1,…,n. We associate a weight 1 to all edges of the path (x 1,x 2),(x 2,x 3),…,(x n−1,x n ) and to edges \((x_{i}^{r},x_{i+1})\) and \((x_{i},x_{i+1}^{r})\) for i=1,…,n−1 and r=1,…,n, and a weight 0 to all other edges in E′. We set U=n−1.

Fig. 3
figure 3

Construction of an instance of Min Node Blocker MST from an instance of Min Vertex Cover

Full size image

We show that

  1. 1.

    opt(I)≤c⇒opt(I′)≤c

  2. 2.

    opt(I)>cρ⇒opt(I′)>cρ

which establishes that Min Node Blocker MST is NP-hard to approximate within a factor 1.36, since Min Vertex Cover is NP-hard to approximate within a factor 1.36 (Dinur and Safra 2005).

1. Let V ∗⊆V be a minimum vertex cover in G. By deleting the nodes of V ∗ from G′, the nodes of V\V ∗ form an independent set in G′−V ∗. Then, connecting any two nodes x i ,x j in G′−V ∗ requires to use a path of weight at least 1. Thus, a minimum spanning tree in G′−V ∗, of weight U=n−1, is obtained by connecting the nodes x i through the path x 1,x 2,…,x n and each node v i ∈V\V ∗ and \(x_{i}^{r}\) to node x i , for i=1,…,n and r=1,…,n. Therefore, we get opt(I′)≤opt(I)≤c.

2. Suppose now that opt(I)>cρ. When we remove all nodes v i , i=1,…,n from G′, the weight of a minimum spanning tree in the resulting graph is U. Hence, opt(I′)≤n. Let N⊆V′ be an optimal solution. If N contains nodes x i or \(x_{i}^{\ell}\) for a given i and ℓ, then N must contain all the nodes x i and \(x_{i}^{r}\) for r=1,…,n, otherwise the weight of a minimum spanning tree in G′−N is the same as in G′−(N\{x i }) or \(G^{\prime}-(N\backslash \{x_{i}^{\ell}\})\). Therefore, since opt(I′)≤n, we can consider in the following that N is included in V. We show in the following that N is a vertex cover in G. Suppose that there exists an edge (v i ,v j )∈E such that v i ∉N and v j ∉N. By deleting N from G′, the weight of a minimum spanning tree in G′−N is at most equal to n−2. Indeed, in such a minimum spanning tree the nodes x i ,v i ,v j ,x j are not connected by the edges (v i ,x i ), (x j ,v j ) and the path on X from x i to x j but by the path (x i ,v i ),(v i ,v j ),(v j ,x j ) of weight 0, thus contradicting the fact that the weight of a minimum spanning tree in G′−N must be at least n−1. Thus, N is a vertex cover in G and opt(I)≤val(I,N)=val(I′,N)=opt(I′) and then opt(I′)>cρ. □

7 Conclusions

As a first result, we established or strengthened the NP-hardness of the four studied problems. Regarding approximation, negative results were obtained only for the node related versions and positive results were obtained only for k Most Vital Edges MST. This situation, combined with our reductions from edge related versions to node related versions (see Theorems 2 and 6, and Corollary 3) clearly shows that node related versions are more difficult than edge related versions. An interesting perspective is to look for approximability results for k Most Vital Nodes MST and Min Edge (Node) blocker MST and for inapproximability results for edge related versions.