Hardness and approximation results for packing Steiner trees
We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees. For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for four terminals. For packing Steiner-node-disjoint Steiner trees of undirected graphs, we show a logarithmic hardness result, and give an approximation guarantee of O(root n log n), where n denotes the number of nodes. For the directed setting (packing edge-disjoint Steiner trees of directed graphs), we show a hardness result of Omega(m(1/3-epsilon)) and give an approximation guarantee of O(m(1/2+epsilon)), where m denotes the number of edges. We have similar results for packing Steiner-node-disjoint priority Steiner trees of undirected graphs.
steiner trees approximation algorithms hardness of approximation packing problems