  In this study, we investigate the problem of classifying, characterizing, and
designing efficient algorithms for hard inference problems on planar graphs, in
the limit of infinite size. The problem is considered hard if, for a
deterministic graph, it belongs to the NP class of computational complexity. A
typical example rich in applications is that of connectivity loss in evacuation
models for natural hazards management (e.g. coastal floods, hurricanes).
Algorithmically, this model reduces to solving a min-cut (or max-flow) problem,
with is known to be intractable. The current work covers several
generalizations: posing the same problem for non-directed networks subject to
random fluctuations (specifically, random graphs from the Erd\"os-R\'enyi
class); finding efficient convex classifiers for the associated decision
problem (deciding whether the graph had become disconnected or not); and the
role played by choice of topology (on the space of random graphs) in designing
efficient, convex approximation algorithms (in the infinite-size limit of the
graph).
