Steiner Tree optimization

Question

I have a NetworkX graph corresponding to a mix of road and telecommunication network of a town, and different sets of nodes (of variable size) representing the location of network devices. I have to find an optimal path connecting all devices along the network and I tought the steiner_tree algorithmn available in NetworkX should do the trick.

Most of the time I get results within a reasonable time and with a reasonable use of resources (i.e. RAM). Sometimes however, when working with graph of few thousands nodes (around 5000) the process takes longer and eats a great amount of RAM.

I am searching for ways to reduce the complexity of the graph and I found the contracted_nodes function in networkx.algorithms.minors module. I use it to "contract" any node with a degree of 2, obtaining a single edge out of a sequence of consecutive edges.

The contracted_nodes has an optional self_loop parameter with the effect of preserving contracted edges as self loops.

Which can be the effects, if any, of these self loops on the steiner_tree algorithm?

Answer 1

You can contract all nodes of degree 2 except for the terminals (the nodes that should always be in your tree). The reason is that you will never have a non-terminal node as a leaf in an optimal Steiner tree, otherwise you could just remove it from the tree. You don't need the self loops. As a side note: the Steiner tree algorithm in networkxx is not only quite slow, but also does not provide optimal solutions. You can get much faster and better results with https://scipjack.zib.de/