Precise knowledge of causal directed acyclic graphs (DAGs) is assumed for standard approaches towards valid adjustment set selection for unbiased estimation, but in practice, the DAG is often inferred from data or expert knowledge, introducing uncertainty. We present techniques to identify valid adjustment sets despite potential errors in the estimated causal graph. Specifically, we assume that only the skeleton of the DAG is known. Under a Bayesian framework, we place a prior on graphs and wish to sample graphs and compute the posterior probability of each set being valid; however, directly doing so is inefficient as the number of sets grows exponentially with the number of nodes in the DAG. We develop theory and techniques so that a limited number of sets are tested while the probability of finding valid adjustment sets remains high. Empirical results demonstrate the effectiveness of the method.