# Is the problem of maximizing the weight loss in a spanning tree with edge restoration NP-hard?

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:

1. $$k$$ is part of the input and $$l$$ is constant.
2. 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.

• – D.W.
Commented Sep 1 at 2:22