Given a graph G with positive edge costs and a subset R of required vertices, the Steiner problem is the determination of a tree in G of minimum total cost spanning R. Several heuristics have been developed for this NP-hard problem. It is well known that any minimum spanning tree T and R for the distance graph of G provides a 2-approximate solution. The tree can often be improved by inserting at most s other vertices into R at a time and repeating while an improvement is possible. Introducing a class of such heuristics INSERT(s), where s=1 corresponds to Minoux's heuristic, we present difficult examples for them and raise a strong conjecture that such heuristics gaurantee to come arbitarily close to the optimum cost in a polynomial time.
