A statistical mechanics approach to the directed Steiner problem on networks

The well-known Steiner problem on networks is an NP-complete problem for which there are many heuristic and exact algorithms that are deterministic. A new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of the method of simulated annealing. A methodology is presented for tailoring a well-known dynamic version of annealing to the directed Steiner problem. Then computations are done on a test bed of 480 random graphs to study the performance of this algorithm. In addition to the quality of the final answers, the study looks at the distribution of first occurrences during the execution of the cooling schedule of answers that are within 3% of the optimum. The study suggests that these near-optimum answers appear according to an approximately exponential distribution and that they can be obtained in polynomial time