The Steiner Tree Problem is a classical network design problem. Given a graph  \(G=(V,E)\) , a cost function \(c:E\rightarrow \mathbb {R}_{\ge 0}\) and a subset  \(R\subseteq V\) of vertices, the goal is to find a minimum cost subtree of G containing all terminal nodes, i.e. all nodes from R. We study Partial Scenario Steiner Tree (PSST) where the terminal set R is uncertain: One is given a collection \(\mathcal {U} = \{\xi _1,\ldots ,\xi _k\}\subseteq 2^V\) of (terminal set) scenarios and the goal is to find a minimum cost subtree of G which completely contains at least a prespecified number l of the scenarios from  \(\mathcal {U}\) . PSST is a special case of Partial Scenario Set Cover (PSSC) which generalizes the Partial Set Cover Problem, which is itself a generalization of the classical Set Cover Problem. In PSSC we are given a finite ground set Q, a collection \(\mathcal {S}\) of subsets of Q to choose from, each of which is associated with a nonnegative cost, and a second collection \(\mathcal {U}\) of subsets of Q of which a given number l must be covered. The task is to choose a minimum cost sub-collection from \(\mathcal {S}\) that covers at least l sets from \(\mathcal {U}\) . Although we focus on PSST, we also consider several other graph-theoretic cases of PSSC. These problems are as hard to approximate as the Smallest k-Edge Subgraph problem. We present simple approximation algorithms which exploit the graph theoretic nature of these problems. Our findings not only shed light on the inherent difficulty of these problems but also provide practical solutions for their approximation.