<p>We can prove NP-hardness by embedding an NP-complete selection problem (such as 3-SAT or Subset-Sum) into this two-stage robust spanning-tree framework. We begin by constructing a graph <span class="math-container">$G=(V,E,w)$</span> with two types of edges: &quot;indicator edges&quot; of very large weight <span class="math-container">$M$</span>, each encoding a particular choice (for instance, truth assignment or subset selection), and a network of lower-weight edges that keep the graph connected. If the chosen spanning tree <span class="math-container">$S$</span> encodes an invalid solution (e.g., a contradictory set of variable assignments), then there exist two large-weight edges in <span class="math-container">$S$</span> whose simultaneous removal (by the adversary) forces the final forest to lose almost all high-weight contribution, because re-adding just one edge cannot recover enough weight to reach some threshold <span class="math-container">$T$</span>. Conversely, if <span class="math-container">$S$</span> represents a valid solution, the adversary's deletion of any two edges cannot prevent us from reinserting at least one high-weight edge and keeping the final total above <span class="math-container">$T$</span>. Therefore, determining whether there exists an <span class="math-container">$S$</span> guaranteeing final weight <span class="math-container">$\ge T$</span> is at least as hard as solving the underlying NP-complete problem, so no polynomial-time method exists unless <span class="math-container">$\mathrm{P}=\mathrm{NP}$</span>.</p>
<p>A useful way to see why the adversary's optimal deletion set <span class="math-container">$D$</span> need not simply be &quot;the two heaviest edges of <span class="math-container">$S$</span>&quot; is that the adversary is optimizing after anticipating our single-edge addition. In other words, the adversary must consider not only which edges it removes from <span class="math-container">$S$</span>, but also which edges remain available in <span class="math-container">$G \setminus D$</span> for us to add back. In some instances—like the four-node example with edges <span class="math-container">$ab=3$</span>, <span class="math-container">$ad=3$</span>, <span class="math-container">$bc=5$</span>, <span class="math-container">$cd=8$</span>, <span class="math-container">$ac=4$</span> and the chosen tree <span class="math-container">$S = \{ab,bc,ad\}$</span>—removing the heaviest edge in <span class="math-container">$S$</span> (<span class="math-container">$ad$</span>) together with a certain high-weight edge not in <span class="math-container">$S$</span> (<span class="math-container">$cd$</span>) can cripple our ability to restore a high-weight cycle (e.g., if <span class="math-container">$cd$</span> were left intact, we could potentially replace <span class="math-container">$ad$</span> by <span class="math-container">$cd$</span>). Formally, the adversary looks to solve
<span class="math-container">$$
\max_{D \subseteq E,\, |D|\le 2} \quad \Bigl(\;\underbrace{\sum_{e \in S\setminus D} w(e)}_{\text{tree edges left}} \;+\;\underbrace{\max_{r\in E\setminus D} w(r \text{ is addable})}_{\text{our best response}}\Bigr)^{\!\!\prime\;}
$$</span>
where &quot;<span class="math-container">$\max(\cdots){\prime}$</span>&quot; indicates the adversary is minimizing our final value. This sometimes requires removing one edge from <span class="math-container">$S$</span> (to reduce its current weight) plus one key edge outside <span class="math-container">$S$</span> (to prevent us from adding it), rather than simply removing the top two edges of <span class="math-container">$S$</span>. If one of the &quot;heaviest&quot; edges outside <span class="math-container">$S$</span> is left available, we might plug it in and recover a large portion of our total. So whenever there is a potentially large-weight edge in <span class="math-container">$G \setminus S$</span> that can be added (forming a cycle or connecting two components after a deletion), the adversary might gain more by removing that edge instead of a second large edge in <span class="math-container">$S$</span>.</p>

CC BY-SA 4.0
2024-12-22T20:54:27.983Z
Sorry but I don't really understand the following points in your reduction process: the exact value of $M$, how to construct the graph specifically and how to set the threshold $T$
Toyllo
CC BY-SA 4.0
2024-12-22T18:18:06.907Z
2024-12-22T18:18:06.907Z
Alex Rudimer
<p>Consider the following combinatorial optimization problem in an undirected weighted graph.
Given:
A connected undirected graph <span class="math-container">$G = (V, E, w)$</span> where: <span class="math-container">$ w: E \rightarrow \mathbb{R}_{\geq 0}$</span> assigns non-negative weights to the edges.</p>
<p>The problem can be aso seen as a two-stage game between us and an adversary, consisting of the following steps:</p>
<p><strong>First Stage (Our Move):</strong></p>
<p>We select a set of edges <span class="math-container">$S$</span>, forming a spanning tree in <span class="math-container">$ G $</span>.</p>
<p><strong>Second Stage (Adversary's Move and Our Response):</strong></p>
<p>The adversary deletes <strong>up to</strong> 2 edges from <span class="math-container">$E$</span>. We denote these deleted edges as set <span class="math-container">$D$</span>. The adversary aims to choose edges to maximize our loss, considering that we may respond in the next step. Note that the adversary can choose <strong>any</strong> edge in <strong><span class="math-container">$G$</span></strong> to delete.</p>
<p>After the adversary's action, we can add <strong>up to</strong> 1 edge from <span class="math-container">$ E \setminus D$</span> to <span class="math-container">$ (S \setminus D)$</span>. Our added edge <span class="math-container">$R$</span>  must be chosen such that the resulting edge set <span class="math-container">$S' = (S \setminus D) \cup R$</span>
still forms a forest. Our goal in this step is to compensate for the loss caused by the adversary's deletion by adding edge that maximize the total weight of the final forest <span class="math-container">$S' $</span>.</p>
<p>The overall goal is to choose <strong>an initial spanning tree</strong> <span class="math-container">$S$</span> to maximize the minimum total weight of the final forest <span class="math-container">$ S'$</span>, considering the worst-case action of the adversary and our best possible response.</p>
<p>For example there is a graph consisting of four nodes, with edge weight <span class="math-container">$ab=3,ad=3,bc=5,cd=8,ac=4$</span>. The optimal <span class="math-container">$S$</span> is <span class="math-container">$ab-bc-ad$</span>. <span class="math-container">$D$</span> is <span class="math-container">$cd$</span> and <span class="math-container">$ad$</span>, <span class="math-container">$R$</span> is empty set.</p>
<p>Is this problem NP-hard? While we can brute force search for all combinations of deleted and added edges, these depend on the <span class="math-container">$S$</span> we choose. And there doesn't seem to be a good way to choose <span class="math-container">$S$</span>. I'm having trouble trying to give reduction, mainly because it's hard to find similar known NP-hard problems. Any proofs, or references to similar problems are greatly appreciated.</p>

CC BY-SA 4.0
2024-11-20T05:56:25.800Z
Can you characterize any properties of the optimal $D$?  For instance, must $D$ always be the two heaviest edges of $S$?
D.W.
CC BY-SA 4.0
2024-11-20T16:14:22.767Z
optimal $D$ be the 2 edges of $G$(not always in $S$), which causes maximum weight loss to us after we add 1 edge back (So $D$ donot need always to be the two heaviest edge). Since the adversary will consider the effect of our adding edges, there are times when the adversary will delete edges in $G\setminus S$
Toyllo
CC BY-SA 4.0
2024-11-20T16:16:20.563Z
For example I have a graph consisting of four nodes, with edge weight $ab=3,ad=3,bc=5,cd=8,ac=4$. The optimal $S$ is $ab-bc-ad$. $D$ is $cd$ and $ad$, $R$ is empty set.
Toyllo
CC BY-SA 4.0
2024-11-21T10:21:22.260Z
Some observations: 1. optimal S are always maximal (because the adversary can also delete edges not in S so there is no advantage of choosing a non-maximal forest S in the first step). 2. We can assume that the graph is connected and thus S is a tree (if not, solve the problem for each connected component individually) 3. For optimal S the adversary always removes at least one edge from S. 4. For unit weights the problem is easy: only bridges and two-cuts of G are relevant.
badboul
CC BY-SA 4.0
2024-11-21T18:11:15.677Z
I don't quite understand your first point where you say that $S$ is always maximal. Look at the example I gave, the optimal $S$ is not a maximal spanning tree (forest)
Toyllo
CC BY-SA 4.0
2024-12-02T13:31:37.827Z
In your example, $S$ is not maximum but it is maximal (i.e. you cannot add any additional edge to $S$).
badboul
CC BY-SA 4.0
2024-12-03T11:09:07.207Z
Yes I think there must be at least one optimal solution $S$ among all spanning trees. But it still not lead to a polynomial time algorithm.
Toyllo
CC BY-SA 4.0
2024-12-30T18:57:33.417Z
Are the weights in unary or binary? Moreover (without thinking too much about the problem) if D consists of a single edge then is the problem any easier?
SamiD
CC BY-SA 4.0
2024-12-30T19:38:19.793Z
Thinking slightly more I guess it is true that in the |D| = 1 version of the problem, we want to end up with the tree S’ (or forest if D were a cut-edge) of maximum weight in E\D? Thus it makes sense to run max version of Kruskal (in which you sort the edges in non-increasing order and add the ones which do not form a cycle with the previous ones) — so,that the replacement edge is the heaviest edge across the cut formed by deleting D — this is bound to work because the tree thus formed tallies with the heaviest tree in E \ D. The question can be reformulated as: What about |D| <= 2?
SamiD
CC BY-SA 4.0
2024-12-30T19:45:10.750Z
I again guess that a similar greedy strategy works for D of size 2 viz. find the maximum spanning tree — now the deletion of any two edges can be (partially) compensated by the heaviest edge across some two of the connected components. I hope I am not missing something important here (like this question being part of a running take home exam ;-)
SamiD
CC BY-SA 4.0
2024-12-30T19:45:17.637Z
In fact as long as $|D| \leq |R|$, the maximum spanning tree can provide the optimal S.
Toyllo
CC BY-SA 4.0
2024-12-30T19:49:23.203Z
I'm not quite sure what greedy strategy you're talking about? If it means that maximum spanning trees are optimal, then the greedy strategy donnot always works. The example I give with 4 nodes already shows this point.
Toyllo
CC BY-SA 4.0
2024-12-30T19:56:00.073Z
I am a bit confused — if you are referring to the figure in https://cs.stackexchange.com/questions/169348/how-to-prove-following-weighted-forest-problem-is-np-hard then i don’t see why the heaviest tree containing 4,5,8 weight edges is not the optimal solution. Sorry if I am missing something obvious.
SamiD
CC BY-SA 4.0
2024-12-30T20:06:06.843Z
The adversary can kill edge 5 and 8, we get final weight of 4+3=7. But If we choose 3,3,5. Then we can have final weight of 8.
Toyllo
CC BY-SA 4.0
2024-12-31T12:22:23.823Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/156902/discussion-between-toyllo-and-samid).
Toyllo
<cc.complexity-theory><graph-theory><graph-algorithms><np-hardness><two-player-games>
Is the following spanning tree problem NP-hard or solvable in polynomial time?
Toyllo
# Is the following spanning tree problem NP-hard or solvable in polynomial time?

(Asked by: username_0 on 2024-11-19)

Consider the following combinatorial optimization problem in an undirected weighted graph.
Given:
A connected undirected graph $G = (V, E, w)$ where: $ w: E \rightarrow \mathbb{R}\_{\geq 0}$ assigns non-negative weights to the edges.

The problem can be aso seen as a two-stage game between us and an adversary, consisting of the following steps:

**First Stage (Our Move):**

We select a set of edges $S$, forming a spanning tree in $ G $.

**Second Stage (Adversary's Move and Our Response):**

The adversary deletes **up to** 2 edges from $E$. We denote these deleted edges as set $D$. The adversary aims to choose edges to maximize our loss, considering that we may respond in the next step. Note that the adversary can choose **any** edge in **$G$** to delete.

After the adversary's action, we can add **up to** 1 edge from $ E \setminus D$ to $ (S \setminus D)$. Our added edge $R$ must be chosen such that the resulting edge set $S' = (S \setminus D) \cup R$
still forms a forest. Our goal in this step is to compensate for the loss caused by the adversary's deletion by adding edge that maximize the total weight of the final forest $S' $.

The overall goal is to choose **an initial spanning tree** $S$ to maximize the minimum total weight of the final forest $ S'$, considering the worst-case action of the adversary and our best possible response.

For example there is a graph consisting of four nodes, with edge weight $ab=3,ad=3,bc=5,cd=8,ac=4$. The optimal $S$ is $ab-bc-ad$. $D$ is $cd$ and $ad$, $R$ is empty set.

Is this problem NP-hard? While we can brute force search for all combinations of deleted and added edges, these depend on the $S$ we choose. And there doesn't seem to be a good way to choose $S$. I'm having trouble trying to give reduction, mainly because it's hard to find similar known NP-hard problems. Any proofs, or references to similar problems are greatly appreciated.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, np-hardness, two-player-games
> **Comments:**
> **username_1**: Can you characterize any properties of the optimal $D$?  For instance, must $D$ always be the two heaviest edges of $S$?  
> **username_0**: optimal $D$ be the 2 edges of $G$(not always in $S$), which causes maximum weight loss to us after we add 1 edge back (So $D$ donot need always to be the two heaviest edge). Since the adversary will consider the effect of our adding edges, there are times when the adversary will delete edges in $G\setminus S$  
> **username_0**: For example I have a graph consisting of four nodes, with edge weight $ab=3,ad=3,bc=5,cd=8,ac=4$. The optimal $S$ is $ab-bc-ad$. $D$ is $cd$ and $ad$, $R$ is empty set.  
> **username_2**: Some observations: 1. optimal S are always maximal (because the adversary can also delete edges not in S so there is no advantage of choosing a non-maximal forest S in the first step). 2. We can assume that the graph is connected and thus S is a tree (if not, solve the problem for each connected component individually) 3. For optimal S the adversary always removes at least one edge from S. 4. For unit weights the problem is easy: only bridges and two-cuts of G are relevant.  
> **username_0**: I don't quite understand your first point where you say that $S$ is always maximal. Look at the example I gave, the optimal $S$ is not a maximal spanning tree (forest)  
> **username_2**: In your example, $S$ is not maximum but it is maximal (i.e. you cannot add any additional edge to $S$).  
> **username_0**: Yes I think there must be at least one optimal solution $S$ among all spanning trees. But it still not lead to a polynomial time algorithm.  
> **username_3**: Are the weights in unary or binary? Moreover (without thinking too much about the problem) if D consists of a single edge then is the problem any easier?  
> **username_3**: Thinking slightly more I guess it is true that in the |D| = 1 version of the problem, we want to end up with the tree S’ (or forest if D were a cut-edge) of maximum weight in E\D? Thus it makes sense to run max version of Kruskal (in which you sort the edges in non-increasing order and add the ones which do not form a cycle with the previous ones) — so,that the replacement edge is the heaviest edge across the cut formed by deleting D — this is bound to work because the tree thus formed tallies with the heaviest tree in E \ D. The question can be reformulated as: What about |D| <= 2?  
> **username_3**: I again guess that a similar greedy strategy works for D of size 2 viz. find the maximum spanning tree — now the deletion of any two edges can be (partially) compensated by the heaviest edge across some two of the connected components. I hope I am not missing something important here (like this question being part of a running take home exam ;-)  
> **username_0**: In fact as long as $|D| \leq |R|$, the maximum spanning tree can provide the optimal S.  
> **username_0**: I'm not quite sure what greedy strategy you're talking about? If it means that maximum spanning trees are optimal, then the greedy strategy donnot always works. The example I give with 4 nodes already shows this point.  
> **username_3**: I am a bit confused — if you are referring to the figure in https://cs.stackexchange.com/questions/169348/how-to-prove-following-weighted-forest-problem-is-np-hard then i don’t see why the heaviest tree containing 4,5,8 weight edges is not the optimal solution. Sorry if I am missing something obvious.  
> **username_0**: The adversary can kill edge 5 and 8, we get final weight of 4+3=7. But If we choose 3,3,5. Then we can have final weight of 8.  
> **username_0**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/156902/discussion-between-toyllo-and-samid).  

---

## 1 answers

### Answer by username_4 on 2024-12-22. Score: -3

We can prove NP-hardness by embedding an NP-complete selection problem (such as 3-SAT or Subset-Sum) into this two-stage robust spanning-tree framework. We begin by constructing a graph $G=(V,E,w)$ with two types of edges: "indicator edges" of very large weight $M$, each encoding a particular choice (for instance, truth assignment or subset selection), and a network of lower-weight edges that keep the graph connected. If the chosen spanning tree $S$ encodes an invalid solution (e.g., a contradictory set of variable assignments), then there exist two large-weight edges in $S$ whose simultaneous removal (by the adversary) forces the final forest to lose almost all high-weight contribution, because re-adding just one edge cannot recover enough weight to reach some threshold $T$. Conversely, if $S$ represents a valid solution, the adversary's deletion of any two edges cannot prevent us from reinserting at least one high-weight edge and keeping the final total above $T$. Therefore, determining whether there exists an $S$ guaranteeing final weight $\ge T$ is at least as hard as solving the underlying NP-complete problem, so no polynomial-time method exists unless $\mathrm{P}=\mathrm{NP}$.

A useful way to see why the adversary's optimal deletion set $D$ need not simply be "the two heaviest edges of $S$" is that the adversary is optimizing after anticipating our single-edge addition. In other words, the adversary must consider not only which edges it removes from $S$, but also which edges remain available in $G \setminus D$ for us to add back. In some instances—like the four-node example with edges $ab=3$, $ad=3$, $bc=5$, $cd=8$, $ac=4$ and the chosen tree $S = \{ab,bc,ad\}$—removing the heaviest edge in $S$ ($ad$) together with a certain high-weight edge not in $S$ ($cd$) can cripple our ability to restore a high-weight cycle (e.g., if $cd$ were left intact, we could potentially replace $ad$ by $cd$). Formally, the adversary looks to solve
$$
\max\_{D \subseteq E,\, |D|\le 2} \quad \Bigl(\;\underbrace{\sum\_{e \in S\setminus D} w(e)}\_{\text{tree edges left}} \;+\;\underbrace{\max\_{r\in E\setminus D} w(r \text{ is addable})}\_{\text{our best response}}\Bigr)^{\!\!\prime\;}
$$
where "$\max(\cdots){\prime}$" indicates the adversary is minimizing our final value. This sometimes requires removing one edge from $S$ (to reduce its current weight) plus one key edge outside $S$ (to prevent us from adding it), rather than simply removing the top two edges of $S$. If one of the "heaviest" edges outside $S$ is left available, we might plug it in and recover a large portion of our total. So whenever there is a potentially large-weight edge in $G \setminus S$ that can be added (forming a cycle or connecting two components after a deletion), the adversary might gain more by removing that edge instead of a second large edge in $S$.

> **Comments:**
> **username_0**: Sorry but I don't really understand the following points in your reduction process: the exact value of $M$, how to construct the graph specifically and how to set the threshold $T$  

---

