  Warning Propagation is a combinatorial message passing algorithm that unifies
and generalises a wide variety of recursive combinatorial procedures. Special
cases include the Unit Clause Propagation and Pure Literal algorithms for
satisfiability as well as the peeling process for identifying the $k$-core of a
random graph. Here we analyse Warning Propagation in full generality on the
binomial random graph. We prove that under a mild stability assumption Warning
Propagation converges rapidly. In effect, the analysis of the fixed point of
the message passing process on a random graph reduces to analysing the process
on a Galton-Watson tree. This result corroborates and generalises a heuristic
first put forward by Pittel, Spencer and Wormald in their seminal $k$-core
paper (JCTB 1996).
