  We prove a large deviation principle for a greedy exploration process on an
Erd\"os-R\'enyi (ER) graph when the number of nodes goes to infinity. To prove
our main result, we use the general strategy to study large deviations of
processes proposed by Feng and Kurtz, based on the convergence of non-linear
semigroups. The rate function can be expressed in a closed-form formula, and
associated optimization problems can be solved explicitly, providing the large
deviation trajectory. Also, we derive an LDP for the size of the maximum
independent set discovered by such an algorithm and analyze the probability
that it exceeds known bounds for the maximal independent set. We also analyze
the link between these results and the landscape complexity of the independent
set and the exploration dynamic.
