# How to prove following weighted forest problem is NP-hard?

I am studying the following weighted forest problem, which is an optimization problem in graph theory focused on finding optimal forest structures in robust scenarios. The problem is defined as follows:

Given an undirected graph $$G = (V, E, w)$$, where $$V$$ is the set of vertices, $$E$$ is the set of edges, and $$w: E \rightarrow \mathbb{R}^+$$ represents the edge weights. Let $$\mathcal{F}$$ be the family of all forests over $$G$$. The goal is to find a first-stage solution $$S \in \mathcal{F}$$ that maximizes the following:

$$\max_{S \in \mathcal{F}} \min_{D \subseteq E, |D| \leq k} \max_{R \subseteq E \setminus D, |R| \leq \ell} w((S \cup R) \setminus D)$$

Here, $$D$$ is the set of edges removed by an adversary, and $$R$$ is the set of edges re-added after removal.

So the problem consists of two stages:

1. Stage One: You choose a forest $$S$$.
2. Stage Two:
• An adversary can remove up to $$k$$ edges from Graph $$G$$. The set of removed edges is denoted by $$D$$.
• You can then re-add up to $$\ell$$ edges from the remaining edges in the graph. The set of re-added edges is denoted by $$R$$. $$(S \cup R) \setminus D$$ must be a forest or tree.
• The final forest you end up with is $$(S \cup R) \setminus D$$, and its total weight is $$w((S \cup R) \setminus D)$$.

Your goal in the first stage is to choose a forest $$S$$ such that, after the adversary’s worst-case removal and your subsequent recovery action, the weight of the final forest is as large as possible.

I would like to know if this problem is NP-hard. If so, could you please explain in detail how to prove that it is NP-hard or suggest some related reduction methods?

This figure is an example for k=2, l=1. The solid edge is the first stage solution and the red color edge is D. In this example R is empty set. And I would also like to know if this k=2, l=1 version problem is np-hard or not.

• Did you mean $(S \backslash D) \cup R$ rather than $(S \cup R) \backslash D$? If $R \subseteq S$, then $S \cup R = S$.
– mhum
Commented Aug 23 at 1:54
• $R$ is the set of re-added edges and it certainly doesn't belong in the S Commented Aug 23 at 9:59
• I see, $R$ has to be chosen out of edges from the graph that were not picked in $D$. These can all be chosen from $S$, but then they would be edges that (1) were already added to the forest and (2) were not taken away. An optimal player would always choose to re-add edges that were not in $S$, if they had the choice. (But note that sometimes the player has no choice but to add nothing.) Commented Aug 23 at 14:44
• Does $D$ need to be a subset of edges of your chosen forest $S$? According to your text description it does. But according to the problem formulation and the example it does not. Also, does $(S \cup R) \setminus D$ need to be a forest? This is not specified in the problem formulation. Commented Aug 27 at 7:02
• Sorry I've corrected the expression. $D$ doesnt need to be a subset of $S$. The final resulting graph cannot have circles (tree or forest). Commented Aug 27 at 8:41