yet another mst problem

1. Candidate positions of the moved point

Suppose point $r$ is moved. Let $Q$ be the set of the other points, and let $s$ be the point after the move.

Fix any spanning tree in an optimal solution. If $A$ is the set of vertices adjacent to $s$, the part of its weight that depends on the position of $s$ is

$$\sum_{i \in A} |x_s-x_i| + \sum_{i \in A} |y_s-y_i|.$$

The two sums are independent. A sum of absolute differences is minimized at a median, so an optimal $x_s$ can be chosen as the $x$-coordinate of a point in $A$, and an optimal $y_s$ can be chosen as the $y$-coordinate of a point in $A$.

Therefore, it is sufficient to try every combination of an $x$-coordinate and a $y$-coordinate appearing in $Q$. There are at most $(N-1)^2$ candidate positions. If $N=1$, the answer is $0$.

2. Keeping only one MST of the remaining points

Let $G$ be the complete Manhattan graph on $Q$, and let $K$ be any MST of $G$. After adding a candidate point $s$, there is one new edge from $s$ to every point of $Q$.

It is sufficient to keep only the edges of $K$ and these new edges. Consider an MST of the augmented graph that uses as few old edges outside $K$ as possible. Suppose it contains such an edge $e$. On the path between the endpoints of $e$ in $K$, every edge has weight at most the weight of $e$. Removing $e$ from the chosen MST creates a cut, and the path in $K$ contains an edge $f$ crossing this cut. Replacing $e$ with $f$ does not increase the weight and decreases the number of old edges outside $K$, which is a contradiction.

Thus, for each candidate position, we only need to run Kruskal's algorithm on a graph with $|Q|+1$ vertices and $2|Q|-1$ edges.

3. Sorting the new edges in linear time

The edges of $K$ do not change while $r$ is fixed, so they are sorted once. Let the candidate position be $(X,Y)$. Partition the points of $Q$ into four regions.

• $x_i \leq X$, $y_i \leq Y$: the distance is $X+Y-(x_i+y_i)$, so the order is decreasing $x_i+y_i$.
• $x_i \leq X$, $y_i > Y$: the distance is $X-Y+(y_i-x_i)$, so the order is increasing $y_i-x_i$.
• $x_i > X$, $y_i \leq Y$: the distance is $-X+Y+(x_i-y_i)$, so the order is increasing $x_i-y_i$.
• $x_i > X$, $y_i > Y$: the distance is $-X-Y+(x_i+y_i)$, so the order is increasing $x_i+y_i$.

Pre-sort the points by these four keys. For one candidate position, filtering each order by its corresponding region produces four sorted streams of edges incident to $s$. Merge these streams together with the sorted edges of $K$ while running Kruskal's algorithm. This takes $O(N)$ time per candidate.

4. Complete algorithm

For every choice of the moved point $r$:

• Build an MST $K$ of the complete Manhattan graph on $Q$ using Prim's algorithm.
• Try every combination of a distinct $x$-coordinate and a distinct $y$-coordinate appearing in $Q$.
• For each candidate, merge the edges of $K$ and the four sorted streams of edges incident to $s$, and run Kruskal's algorithm.

The first observation guarantees that some optimal moved position is considered. The second observation guarantees that the MST weight for every considered position is computed exactly. Since every original point is considered as the moved point, the minimum found by the algorithm is the answer.

There are $O(N^2)$ candidate positions for each moved point, and each candidate is processed in $O(N)$ time. Over all choices of the moved point, the time complexity is $O(N^4)$ and the memory complexity is $O(N^2)$.

Solution written by GPT5.6