  In dense Erd\H{o}s-R\'enyi random graphs, we are interested in the events
where large numbers of a given subgraph occur. The mean behavior of subgraph
counts is known, and only recently were the related large deviations results
discovered. Consequently, it is natural to ask, can one develop efficient
numerical schemes to estimate the probability of an Erd\H{o}s-R\'enyi graph
containing an excessively large number of a fixed given subgraph? Using the
large deviation principle we study an importance sampling scheme as a method to
numerically compute the small probabilities of large triangle counts occurring
within Erd\H{o}s-R\'enyi graphs. We show that the exponential tilt suggested
directly by the large deviation principle does not always yield an optimal
scheme. The exponential tilt used in the importance sampling scheme comes from
a generalized class of exponential random graphs. Asymptotic optimality, a
measure of the efficiency of the importance sampling scheme, is achieved by a
special choice of the parameters in the exponential random graph that makes it
indistinguishable from an Erd\H{o}s-R\'enyi graph conditioned to have many
triangles in the large network limit. We show how this choice can be made for
the conditioned Erd\H{o}s-R\'enyi graphs both in the replica symmetric phase as
well as in parts of the replica breaking phase to yield asymptotically optimal
numerical schemes to estimate this rare event probability.
