7
$\begingroup$

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?.

$\endgroup$
  • 3
    $\begingroup$ This is the uniform cost version of the spanning tree interdiction problem. See arxiv.org/abs/1508.01448 and references there. $\endgroup$ – Chandra Chekuri Jun 8 '16 at 15:55
  • 2
    $\begingroup$ 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? $\endgroup$ – R B Jun 9 '16 at 5:23
  • $\begingroup$ @R B, I am not claiming anything. Just giving you a reference to follow up. $\endgroup$ – Chandra Chekuri Jun 9 '16 at 15:53
  • $\begingroup$ Are negative weights allowed? $\endgroup$ – Chandra Chekuri Jun 11 '16 at 20:26
  • $\begingroup$ @ChandraChekuri - both variants are interesting. For my application, positive integer weights are enough. $\endgroup$ – R B Jun 12 '16 at 10:46
6
$\begingroup$

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:

  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." 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$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Austin Buchanan Jun 10 '16 at 6:14
  • $\begingroup$ @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. $\endgroup$ – Chandra Chekuri Jun 10 '16 at 14:24
  • 1
    $\begingroup$ @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? $\endgroup$ – Austin Buchanan Jun 10 '16 at 15:03
  • $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Jun 10 '16 at 19:31
  • $\begingroup$ @AustinBuchanan It looks like I misread the OP's question in exactly the same way as Chandra Chekuri did. $\endgroup$ – mhum Jun 10 '16 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.