Computational complexity arising from degree correlations in networks
<|reference_start|>Computational complexity arising from degree correlations in networks: 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.<|reference_end|>
@article{vazquez2002computational,
    title={Computational complexity arising from degree correlations in networks},
    author={Alexei Vazquez and Martin Weigt},
    journal={Phys. Rev. E 67, 027101 (2003)},
    year={2002},
    doi={10.1103/PhysRevE.67.027101},
    archivePrefix={arXiv},
    eprint={cond-mat/0207035},
    primaryClass={cond-mat.dis-nn cond-mat.stat-mech cs.CC}
}