THE COMPUTATIONAL-COMPLEXITY OF STEINER TREE PROBLEMS IN GRADED MATRICES

We investigate the computational complexity of the Steiner tree proble m in graphs when the distance matrix is graded, i.e., has increasing, respectively, decreasing rows, or increasing, respectively, decreasing columns, or both. We exactly characterize polynomially solvable and N P-hard variants, and thus, establish a sharp borderline between easy a nd difficult cases of this optimization problem.