<p><strong>EDIT</strong></p>

<p>As noted in comments below, I originally read the question incorrectly. I thought the goal was to determine if removing $k$ edges could increase the MST weight of $G$ above some given threshold $t$. This problem is often known as "$k$ Most Vital Edges (for MST)", simply $k$-MVE (or sometimes $k$-MVE-MST to distinguish from other variations), as cited in my original answer. However, the asker poses instead the question of whether or not removing $k$ edges could increase the MST weight of $G$ <em>by any amount</em>. Let's call this problem "$k$ Any Vital Edges" or $k$-AVE. We will show that $k$-AVE is in <strong>P</strong>.</p>

<p>Let $G=(V,E)$ be an edge-weighted graph with weight function $w:E\rightarrow \mathbb{N}$. The goal of $k$-AVE is to find a subset of edges $S \subseteq E$ of size $k$ such that the MST weight of $G$ is strictly less than the MST weight of $G\setminus S \triangleq (V, E\setminus S)$. We'll call such an $S$ a <em>valid</em> $k$-AVE set. We will proceed by outlining necessary and sufficient conditions for $S$ to be a valid $k$-AVE set.</p>

<p>Let $T$ be a MST of $G$. For every edge $e \in T$, we may associate a partition of $V$ into two parts (i.e.: a cut) based on how $e$ splits $T$ (i.e.: each partition consists of the vertices reachable from either endpoint of $e$ using only edges in $T \setminus \{e\}$). In particular, we will denote by $C_e$ the cut-set of this associated partition (i.e.: set of edges in $G$ that straddle this partition, including $e$ itself). </p>

<p>Now, by the <a href="https://en.wikipedia.org/wiki/Minimum_spanning_tree#Cut_property" rel="nofollow">Cut Property</a> of MSTs, we know that each $e$ has minimum weight among all edges in $C_e$; there may be more than one edge in $C_e$ with that same minimum weight. Let these sets be denoted $M_e \triangleq \{e' \in C_e | w(e') = w(e)\}$. Suppose that, for some $e$, $M_e\subseteq S$. Then, we conclude that $G\setminus S$ has larger MST weight than $G$. Otherwise, we would have some MST $T'$ in $G$ that did not use any of the minimum weight edges across the cut-set $C_e$, a contradiction of the Cut Property. This shows that a sufficient condition for $S$ to be a valid $k$-AVE set is for it to contain $M_e$ for some $e$.</p>

<p>Next, we will show that this is condition is also necessary. Suppose to the contrary that, for all $e\in T$, $S$ excludes some $e' \in M_e$ (of course allowing that $e'$ may equal $e$). In general, removing $S$ from $G$ splits $T$ into a forest. We will reconstruct a new minimum spanning tree $T'$ from $T\setminus S$ by using the edges spared by $S$, as follows:</p>

<blockquote>
  <ol>
  <li>Let $T' = T\setminus S$</li>
  <li>For each $e$ in $T$ do</li>
  <li>$\qquad$If no edge in $T'$ spans $C_e$ then let $T' = T' \cup \{e'\}$ </li>
  <li>Return $T'$</li>
  </ol>
</blockquote>

<p>We leave as an exercise to the reader to prove that this procedure reconstructs a spanning tree $T'$ with the same weight as $T$. (Outline: each edge added in step 3 preserves acyclicity and no components of $T\setminus S$ can remain separated).</p>

<p>These necessary and sufficient criteria naturally suggest a poly-time algorithm for determining if $G$ has a valid $k$-AVE set. First, construct a MST $T$. For each $e\in T$, we compute the cut-set $C_e$ and the set of minimum weight edges in $C_e$, $M_e$. If for some $e$, $|M_e| \leq k$, then we can simply take any $S \supseteq M_e$ as our valid $k$-AVE set. Otherwise, if all $M_e$ sets are larger than size $k$, we conclude that $G$ has no $k$-AVE set.</p>

<hr>

<p><em>Original Answer Below</em></p>

<p>Shen, Hong. "<a href="http://link.springer.com/article/10.1007/s002360050166" rel="nofollow">Finding the k most vital edges with respect to minimum spanning tree.</a>" Acta Informatica 36.5 (1999): 405-424.</p>

<blockquote>
  <p>For a connected, undirected and weighted graph $G = (V,E)$, the problem of finding the $k$ most vital edges of $G$ with respect to minimum spanning tree is to find $k$ edges in $G$ whose removal will cause greatest weight increase in the minimum spanning tree of the remaining graph. This problem is known to be NP-hard for arbitrary $k$.</p>
</blockquote>

CC BY-SA 3.0
2016-06-10T06:14:43.423Z
This does not answer the OP's question. The OP's problem is simpler in that asks to find *any* subset of $k$ edges whose removal increases the MST cost, while your quote is for $k$-edge subsets whose removal increases the MST cost *as much as possible*.
Austin Buchanan
CC BY-SA 3.0
2016-06-10T14:24:39.740Z
@AustinBuchanan, I think it does. Basically the OP's question is a decision problem where the weight of the MST increases to at least a given amount. If the OP's problem is poly-time solvable then the optimization problem considered in the paper mentioned in the paper above would also be solvable in polynomial time.
Chandra Chekuri
CC BY-SA 3.0
2016-06-10T15:03:38.660Z
@ChandraChekuri Could you sketch the algorithm that you have in mind for solving the optimization variant when given an oracle for solving the OP's decision problem?
Austin Buchanan
CC BY-SA 3.0
2016-06-10T19:31:18.017Z
I realize that I misunderstood the OP's question. I somehow thought that $w(G)$ was an arbitrary input parameter $w$. I take back my previous comment. Now I see by OP was unsure of my comment on interdiction.
Chandra Chekuri
CC BY-SA 3.0
2016-06-10T19:49:08.430Z
@AustinBuchanan It looks like I misread the OP's question in exactly the same way as Chandra Chekuri did.
mhum
CC BY-SA 3.0
2016-06-09T18:08:09.587Z
2016-06-24T01:02:15.433Z
2016-06-24T01:02:15.433Z
mhum
<p>Assume we have a connected input graph $G=(V,E)$ and a weight function $w:E\to\mathbb N$.
Denote by $w(G)$ the weight of a minimum spanning gree for a graph $G$. For this purpose, define $w(G')$ as $\infty$ for graph $G'$ which is not connected.</p>

<p>Consider the following problem:</p>

<blockquote>
  <p>Given an integer $k\in\mathbb N$, decide whether there exists an edge set $E'\subseteq E$ , such that $|E'|=k$ and $w((V,E\setminus E')) &gt; w(G)$?</p>
</blockquote>

<p><strong>What is the complexity of the above problem?</strong>.</p>

CC BY-SA 3.0
2016-06-08T15:55:23.040Z
This is the uniform cost version of the spanning tree interdiction problem. See http://arxiv.org/abs/1508.01448 and references there.
Chandra Chekuri
CC BY-SA 3.0
2016-06-09T05:23:04.633Z
Thanks @ChandraChekuri, but I'm not sure this is exactly the same problem. For example, shortest $s,t$-path interdiction is NP-hard (if you try to maximize the path length), but if you are only asking for the number of edges whose removal increase the length of the shortest path, it is poly-time solvable (using min-cut on the shortest edges graph). Do you see a direct reduction showing this problem is hard?
R B
CC BY-SA 3.0
2016-06-09T15:53:04.373Z
@R B, I am not claiming anything. Just giving you a reference to follow up.
Chandra Chekuri
CC BY-SA 3.0
2016-06-11T20:26:39.120Z
Are negative weights allowed?
Chandra Chekuri
CC BY-SA 3.0
2016-06-12T10:46:08.230Z
@ChandraChekuri - both variants are interesting. For my application, positive integer weights are enough.
R B
<cc.complexity-theory><ds.algorithms><graph-theory><graph-algorithms><tree>
Complexity of "destroying" the graph's minimum spanning tree weight
R B
# Complexity of "destroying" the graph's minimum spanning tree weight

(Asked by: username_0 on 2016-06-08)

Assume we have a connected input graph $G=(V,E)$ and a weight function $w:E\to\mathbb N$.
Denote by $w(G)$ the weight of a minimum spanning gree for a graph $G$. For this purpose, define $w(G')$ as $\infty$ for graph $G'$ which is not connected.

Consider the following problem:

> Given an integer $k\in\mathbb N$, decide whether there exists an edge set $E'\subseteq E$ , such that $|E'|=k$ and $w((V,E\setminus E')) > w(G)$?

**What is the complexity of the above problem?**.

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, graph-algorithms, tree
> **Comments:**
> **username_1**: This is the uniform cost version of the spanning tree interdiction problem. See http://arxiv.org/abs/1508.01448 and references there.  
> **username_0**: Thanks @ChandraChekuri, but I'm not sure this is exactly the same problem. For example, shortest $s,t$-path interdiction is NP-hard (if you try to maximize the path length), but if you are only asking for the number of edges whose removal increase the length of the shortest path, it is poly-time solvable (using min-cut on the shortest edges graph). Do you see a direct reduction showing this problem is hard?  
> **username_1**: @R B, I am not claiming anything. Just giving you a reference to follow up.  
> **username_1**: Are negative weights allowed?  
> **username_0**: @ChandraChekuri - both variants are interesting. For my application, positive integer weights are enough.  

---

## 1 answers

### Answer by username_2 on 2016-06-09. Score: 6 | Accepted answer

**EDIT**

As noted in comments below, I originally read the question incorrectly. I thought the goal was to determine if removing $k$ edges could increase the MST weight of $G$ above some given threshold $t$. This problem is often known as "$k$ Most Vital Edges (for MST)", simply $k$-MVE (or sometimes $k$-MVE-MST to distinguish from other variations), as cited in my original answer. However, the asker poses instead the question of whether or not removing $k$ edges could increase the MST weight of $G$ *by any amount*. Let's call this problem "$k$ Any Vital Edges" or $k$-AVE. We will show that $k$-AVE is in **P**.

Let $G=(V,E)$ be an edge-weighted graph with weight function $w:E\rightarrow \mathbb{N}$. The goal of $k$-AVE is to find a subset of edges $S \subseteq E$ of size $k$ such that the MST weight of $G$ is strictly less than the MST weight of $G\setminus S \triangleq (V, E\setminus S)$. We'll call such an $S$ a *valid* $k$-AVE set. We will proceed by outlining necessary and sufficient conditions for $S$ to be a valid $k$-AVE set.

Let $T$ be a MST of $G$. For every edge $e \in T$, we may associate a partition of $V$ into two parts (i.e.: a cut) based on how $e$ splits $T$ (i.e.: each partition consists of the vertices reachable from either endpoint of $e$ using only edges in $T \setminus \{e\}$). In particular, we will denote by $C\_e$ the cut-set of this associated partition (i.e.: set of edges in $G$ that straddle this partition, including $e$ itself).

Now, by the [Cut Property](https://en.wikipedia.org/wiki/Minimum_spanning_tree#Cut_property) of MSTs, we know that each $e$ has minimum weight among all edges in $C\_e$; there may be more than one edge in $C\_e$ with that same minimum weight. Let these sets be denoted $M\_e \triangleq \{e' \in C\_e | w(e') = w(e)\}$. Suppose that, for some $e$, $M\_e\subseteq S$. Then, we conclude that $G\setminus S$ has larger MST weight than $G$. Otherwise, we would have some MST $T'$ in $G$ that did not use any of the minimum weight edges across the cut-set $C\_e$, a contradiction of the Cut Property. This shows that a sufficient condition for $S$ to be a valid $k$-AVE set is for it to contain $M\_e$ for some $e$.

Next, we will show that this is condition is also necessary. Suppose to the contrary that, for all $e\in T$, $S$ excludes some $e' \in M\_e$ (of course allowing that $e'$ may equal $e$). In general, removing $S$ from $G$ splits $T$ into a forest. We will reconstruct a new minimum spanning tree $T'$ from $T\setminus S$ by using the edges spared by $S$, as follows:

> 1. Let $T' = T\setminus S$
> 2. For each $e$ in $T$ do
> 3. $\qquad$If no edge in $T'$ spans $C\_e$ then let $T' = T' \cup \{e'\}$
> 4. Return $T'$

We leave as an exercise to the reader to prove that this procedure reconstructs a spanning tree $T'$ with the same weight as $T$. (Outline: each edge added in step 3 preserves acyclicity and no components of $T\setminus S$ can remain separated).

These necessary and sufficient criteria naturally suggest a poly-time algorithm for determining if $G$ has a valid $k$-AVE set. First, construct a MST $T$. For each $e\in T$, we compute the cut-set $C\_e$ and the set of minimum weight edges in $C\_e$, $M\_e$. If for some $e$, $|M\_e| \leq k$, then we can simply take any $S \supseteq M\_e$ as our valid $k$-AVE set. Otherwise, if all $M\_e$ sets are larger than size $k$, we conclude that $G$ has no $k$-AVE set.

---

*Original Answer Below*

Shen, Hong. "[Finding the k most vital edges with respect to minimum spanning tree.](http://link.springer.com/article/10.1007/s002360050166)" Acta Informatica 36.5 (1999): 405-424.

> For a connected, undirected and weighted graph $G = (V,E)$, the problem of finding the $k$ most vital edges of $G$ with respect to minimum spanning tree is to find $k$ edges in $G$ whose removal will cause greatest weight increase in the minimum spanning tree of the remaining graph. This problem is known to be NP-hard for arbitrary $k$.

> **Comments:**
> **username_3**: This does not answer the OP's question. The OP's problem is simpler in that asks to find *any* subset of $k$ edges whose removal increases the MST cost, while your quote is for $k$-edge subsets whose removal increases the MST cost *as much as possible*.  
> **username_1**: @AustinBuchanan, I think it does. Basically the OP's question is a decision problem where the weight of the MST increases to at least a given amount. If the OP's problem is poly-time solvable then the optimization problem considered in the paper mentioned in the paper above would also be solvable in polynomial time.  
> **username_3**: @ChandraChekuri Could you sketch the algorithm that you have in mind for solving the optimization variant when given an oracle for solving the OP's decision problem?  
> **username_1**: I realize that I misunderstood the OP's question. I somehow thought that $w(G)$ was an arbitrary input parameter $w$. I take back my previous comment. Now I see by OP was unsure of my comment on interdiction.  
> **username_2**: @AustinBuchanan It looks like I misread the OP's question in exactly the same way as Chandra Chekuri did.  

---

