Given $G = (V, E, w)$, an undirected weighted graph, where $V$ is the set of vertices, $E$ is the set of edges, and $w: E \rightarrow \mathbb{R}^+$ is a function assigning positive real weights to the edges. Given a spanning tree $T$ of $G$, we need to select $k$ edges to remove from $T$, resulting in several connected subgraphs. After these edges are removed, the opponent will select $l$ edges from $G/T$ (i.e., edges in $G$ but not in $T$) to add back, excluding any edges that were just removed. The opponent aims to choose $l$ edges that maximize the total weight.
How to select the $k$ edges to remove so as to maximize the total weight loss of the original spanning tree $T$ after the opponent adds back $l$ edges? Here, the weight loss is defined as the total weight of the original spanning tree $T$ minus the total weight of the new tree considering the added back edges. We assume $k$ and $l$ are constants, making the problem solvable in polynomial time.
However, I am interested in understanding the complexity in two scenarios:
- $k$ is part of the input and $l$ is constant.
- Both $k$ and $l$ are part of the input.
I have been attempting to establish NP-hardness through a polynomial-time reduction from the Max-Cut problem, but have not succeeded yet.
