Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?.
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 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:
- Let $T' = T\setminus S$
- For each $e$ in $T$ do
- $\qquad$If no edge in $T'$ spans $C_e$ then let $T' = T' \cup \{e'\}$
- 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." 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$.
