On the complexity of Steiner-like problems