The computational complexity of Steiner tree problems in graded matrices Original Research Article

We investigate the computational complexity of the Steiner tree problem 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 NP-hard variants, and thus, establish a sharp borderline between easy and diffucult cases of this optimization problem.