On the complexities of the incremental bottleneck and bottleneck terminal Steiner tree problems

Given a graph G = (V, E) with non-negative edge lengths, a subset R subset of V, a Steiner tree for R in G is an acyclic subgraph of G interconnecting all vertices in R and a terminal Steiner tree is defined to be a Steiner tree in G with all the vertices of R as its leaves. A bottleneck edge of a Steiner tree is an edge with the largest length in the Steiner tree. The bottleneck Steiner tree problem (BSTP) (respectively, the bottleneck terminal Steiner tree problem (BTSTP)) is to find a Steiner tree (respectively, a terminal Steiner tree) for R in G with minimum length of a bottleneck edge. For any arbitrary tree T, len(b)(T) denotes the length of a bottleneck edge in T. Let T-opt(G, BSTP) and T-opt(G, BTSTP) denote the optimal solutions for the BSTP and the BTSTP in G, respectively. Given a graph G = (V, E) with non-negative edge lengths, a subset E-0 subset of E, a number h = vertical bar E\ E-0 vertical bar, and a subset R subset of V, the incremental bottleneck Steiner tree problem (respectively, the incremental bottleneck terminal Steiner tree problem) is to find a sequence of edge sets {E-0 subset of E-1 subset of E-2 subset of ... subset of E-h = E} with vertical bar E-i \ Ei-1 vertical bar = 1 such that Sigma(h)(i=1) len(b)(T-opt(G(i), BSTP)) (respectively, Sigma(h)(i=1) len(b)(T-opt(G(i), BTSTP))) is minimized, where G(i) = (V, E-i). In this paper, we prove that the incremental bottleneck Steiner tree problem is NP-hard. Then we show that there is no polynomial time approximation algorithm achieving a performance ratio of (1 - epsilon) x ln vertical bar R vertical bar, 0 < epsilon < 1, for the incremental bottleneck terminal Steiner tree problem unless NP subset of DTIME(vertical bar R vertical bar(log) (log) (vertical bar R vertical bar)).