Monte Carlo cluster algorithms are popular for their efficiency in studying the Ising model near its critical temperature. We might expect that this efficiency extends to the bond-diluted Ising model. We show, however, that this is not always the case by comparing how the correlation times $��_w$ and $��_{\rm sw}$ of the Wolff and Swendsen-Wang cluster algorithms scale as a function of the system size $L$ when applied to the two-dimensional bond-diluted Ising model. We demonstrate that the Wolff algorithm suffers from a much longer correlation time than in the pure Ising model, caused by isolated (groups of) spins which are infrequently visited by the algorithm. With a simple argument we prove that these cause the correlation time $��_w$ to be bounded from below by $L^{z_w}$ with a dynamical exponent $z_w=��/ ��\approx 1.75$ for a bond concentration $p < 1$. Furthermore, we numerically show that this lower bound is actually taken for several values of $p$ in the range $0.5 < p < 1$. Moreover, we show that the Swendsen-Wang algorithm does not suffer from the same problem. Consequently, it has a much shorter correlation time, shorter than in the pure Ising model even. Numerically at $p = 0.6$, we find that its dynamical exponent is $z_{\rm sw} = 0.09(4)$.

7 pages, 4 figures