  We apply a Bethe-Peierls approach to statistical-mechanics models defined on
random networks of arbitrary degree distribution and arbitrary correlations
between the degrees of neighboring vertices. Using the NP-hard optimization
problem of finding minimal vertex covers on these graphs, we show that such
correlations may lead to a qualitatively different solution structure as
compared to uncorrelated networks. This results in a higher complexity of the
network in a computational sense: Simple heuristic algorithms fail to find a
minimal vertex cover in the highly correlated case, whereas uncorrelated
networks seem to be simple from the point of view of combinatorial
optimization.
