Minimum product spanning tree with negative weights

Question

Suppose if all the edges have positive Weights the minimum product spanning tree can be obtained by taking the log of every edge and then apply Kruskal or Prim. But if some weights are negative, we can't apply this procedure. since we need to include odd number of negative edges, and those edges must be of the maximum weight. How to do in such case?

Answer 1

I highly doubt you can modify Prims algorithm to work for this problem because negative numbers completely change it. If you manage to get a negative result then the absolute value has to be maximized which means the edges with the highest absolute values have to be used, hence trying to optimize a result found by Prims algo and taking the log(abs()) will not work, unless it is impossible to get a negative result, then this will actually return the best solution.

This makes the problem a little simpler, because we only have to look for the best negative solution and if we don't find any we use Prims with log(abs()).

If we assign each vertice a value of 1, then two vertices can be merged by creating a new vertice with all the edges of both vertices except the one connecting them and the value is the product of the values of the removed vertices and edge.

Based on this we can start to simplify by merging all nodes with only one edge. Parallel to each merge step the removed edge has to be marked as used in the original graph, so that the tree can be reconstructed from the marked edges in the end.

Additionally we can merge all nodes with only positive or only negative edges removing the edge with the highest absolute value. After merging the new node can have several connections to the same node, you can discard all but the negative and positive edge with the highest absolute value (so max 2 edges to the same node). Btw. as soon as we have 2 edges to the same node (following the removal conditions above) we know a solution <= 0 has to exist.

If you end up with one node and it is negative then the problem was solved successfully, if it is positive there is no negative solution. If we have a 0 vertice we can merge the rest of the nodes in any order. More likely we end up with 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 then we want to merge the nodes with an even number of negative edges and vice versa.

Always merge by the edge with the highest absolute value. If the resulting vertice is <= 0 then you found the best solution. Otherwise it gets complicated. You could look at all the unused edges, try to add it, see which edges can be removed to make it a tree again, only look at those with different sign and build the ratio abs(added_edge/removed_edge). Then finally do the change with the best ratio (if you found any combination with opposite signs otherwise there is no negative solution). But I am not 100% sure if this would always give 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 log(abs(edge)) sum. Then, check if the actual product (without abs) is negative. If negative output the current spanning tree, else replace one of the positive edges with a negative edge or negative with positive to get the solution.

If none of the edges are negative, minimizing for log(edge) sum should work.

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

More explanation on naive algorithm: Select the edge that has the lowest absolute value for removal. Removing this edge will split the tree into two parts. We could go through every pair between those sets (should be positive or negative depending on the case) whose edge value is the largest. Complexity of this part is O(n^2).

We might have to try removing multiple edges to reach the best solution. Assuming we go through every edge, complexity is O(n^3).

I am very confident this could be improved though.