Extensions to the Black-Scholes model have been suggested recently that permit one to calculate worst-case prices for a portfolio of vanilla options or for exotic options when no a priori distribution for the forward volatility is known. The Uncertain Volatility Model (UVM) by Avellaneda and Paras finds a one-sided worstcase volatility scenario for the buy resp. sell side within a specified volatility range. A key feature of this approach is the possibility of hedging with options: risk cancellation leads to super resp. sub-additive portfolio values. This nonlinear behaviour causes the combinatorial complexity of the pricing problem to increase significantly in the case of barrier options. In the paper, it is shown that for a portfolio P of n barrier options and any number of vanilla options, the number of PDEs that have to be solved in a hierarchical manner in order to solve the UVM problem for P is bounded by O (n2). A numerically stable implementation is described and numerical results are given.