Minimum spanning tree with negative weights

Question

Suppose that if all the edges have positive weights, the minimum spanning tree can be obtained by taking the log each edge, and then apply Kruskal or Prim. But if some weights are negative, we cannot apply this procedure. since we need to include an odd number of negative edges, and these edges must have maximum weight. How to do it?

Answer 1

I very much doubt that you can modify the Prims algorithm to work on this problem, because negative numbers completely change it. If you manage to get a negative result, you need to maximize the absolute value, which means you need to use edges with the highest absolute values, therefore, trying to optimize the result found by Prims algo and taking log (abs ()) will not work if it is impossible to get a negative result, then it really will return the best solution.

This makes the problem a little easier, because we only need to look for the best negative solution, and if we do not find any, we will use Prims with log (abs ()).

If we assign a value of 1 to each vertex, then the two vertices can be combined by creating a new vertex with all the edges of both vertices, except those that connect them, and the value is the product of the values ​​of the removed vertices and the edge.

Based on this, we can begin to simplify by combining all nodes with only one edge. At the same time as each merge step, the deleted edge should be marked as used in the original graph, so that the tree can be restored from the marked edges at the end.

In addition, we can combine all nodes with only positive or only negative edges that remove the edge with the highest absolute value. After merging, a new node can have several connections to the same node, you can drop everything except negative and positive, with the highest absolute value (so there are a maximum of 2 edges on the same node). Btw. as soon as we have 2 edges to the same node (following the deletion conditions listed above), we know that the solution & lt = 0 must exist.

If you end up with one node and negative, then the problem has been successfully resolved, if it is positive, there is no negative solution. If we have 0 vertex, we can combine the remaining nodes in any order. Most likely, we will get a highly connected graph, where each node has at least one negative and one positive edge. If we have an odd number of negative vertices, we want to combine the nodes with an even number of negative edges and vice versa.

Always align around the edge with the highest absolute value. If the resulting vertex is <= 0, then you have found the best solution. Otherwise, it gets complicated. You can look at all the unused edges, try to add them, see which edges can be removed to create a tree again, look only at those that have a different sign, and create an abs relation (added_for / deleted_for). Then, finally, make the change with the best ratio (if you find any combination with opposite signs, otherwise there is no negative solution). But I'm not 100% sure if it always gave the best result.

Answer 2

Here is a simple solution. If there is at least one negative edge, find the most optimal spanning tree that maximizes the sum of the log (abs (edge)). Then check if the actual product (without abs.) Is Negative. If a negative value displays the current spanning tree, replace one of the positive edges with a negative edge or a negative positive one to get a solution.

If none of the edges is negative, you need to minimize the sum of log (edge).

Difficulty: O (n ^ 2) with a naive solution.

More explanations for the naive algorithm: Select the edge that has the lowest absolute value for deletion. Removing this edge will split the tree into two parts. We could go through each pair between these sets (should be positive or negative depending on the case), the extreme value of which is the largest. The complexity of this part is O (n ^ 2).

We may need to try to remove several edges in order to achieve the best solution. Assuming we go through each edge, the complexity is O (n ^ 3).

I am very sure that this can be improved.