3
$\begingroup$

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 \subseteq \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 your chosen forest. 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 $.
    • 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. This example does not have R. And I would also like to know if this k=2, l=1 version problem is np-hard or not. enter image description here

Improve this question
$\endgroup$
7
  • $\begingroup$ How is the weight calculated for a given set of edges? Just the sum of individual edge weights? In that case it seems you can change "forest" to "induced $P_2$ subgraph" in the problem description retaining its complexity. But it seems the problem is too trivial if so. $\endgroup$
    – rus9384
    Commented Aug 12 at 16:54
  • $\begingroup$ The reason I use forests is to avoid connectivity that can't be guaranteed after $D$ is removed. In the vast majority of cases the first stage solution is necessarily a spanning tree. One can start by considering the case k=2, l=1, in which case I did not find a polynomial time algorithm. $\endgroup$
    – Toyllo
    Commented Aug 12 at 17:21
  • $\begingroup$ Is there a limit on the size of the forest $S$ you choose in the beginning? It seems that nothing stops us from choosing a forest that contains all edges of the maximum spanning forest with $\ell$ heaviest edges removed. $\endgroup$
    – rus9384
    Commented Aug 12 at 20:24
  • $\begingroup$ But thats not 100% optimal solution, pls check the figure, the best solution 5-3-3 is a normal spanningtree. $\endgroup$
    – Toyllo
    Commented Aug 13 at 10:20
  • $\begingroup$ As far as I understand, the player has chosen the tree {AD, AB, BC} on the first move. By the problem specification, the opponent can't remove the edge CD, because it does not belong to the chosen forest. $\endgroup$
    – rus9384
    Commented Aug 13 at 10:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.