Probabilistic reasoning in intelligent systems

Just delving deeper into Pearl & Spiegelhalter's work. I can see why the computation in a space that is the size of the maximal clique? But isn't finding the cliques (maximally fully connected sets) exponential anyway - if you are using heuristics to do that then how are you better off?