On the hardness of optimization in power-law graphs

AbstractOur motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes yi of a given degree i is proportional to i−β where β>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent β? Our main result is the proof that many classical NP-hard graph-theoretic optimization problems remain NP-hard on power-law graphs for certain values of β. In particular, we show that some classical problems, such as CLIQUE and COLORING, remain NP-hard for all β≥1. Moreover, we show that all the problems that satisfy the so-called “optimal substructure property” remain NP-hard for all β>0. This includes classical problems such as MINIMUM VERTEX COVER, MAXIMUM INDEPENDENT SET, and MINIMUM DOMINATING SET. Our proofs involve designing efficient algorithms for constructing graphs with prescribed degree sequences that are tractable with respect to various optimization problems