Lindley Hall 102 (2:15pm-2:45pm)

Gopal Panduragan
Purdue University

Complexity of Combinatorial Optimization in
Power Law Graphs

The elegant theory of NP-hardness serves as an important cornerstone in understanding the difficulty of solving various combinatorial optimization problems in graphs. A natural and relevant question is whether such hardness results are applicable to ``real-world'' graphs since such graphs may possess certain well-defined special properties which may very well make the problems tractable. Our 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 exhibit a power-law distribution: the number of nodes $y$ of a given degree $i$ is proportional to $i^{-\beta}$ where $\beta> 0$ is a constant that depends on the application domain. Thus power-law graphs have emerged as a partial answer to the perennial search for representative real-world graphs (where $\beta$ is typically between 1 and 4) in combinatorial optimization. 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 $\beta$? Our main result is the proof that many classical NP-hard graph-theoretic optimization problems that satisfy the so-called ``optimal substructure property'' remain NP-hard on power law graphs for all $\beta>0$. This includes classical problems such as MINIMUM VERTEX-COVER, MAXIMUM INDEPENDENT-SET, and MINIMUM DOMINATING-SET. Another contribution of the paper is the design of {\em polynomial time} algorithms for graphs with prescribed degree sequences. These algorithms are useful in showing the NP-completeness of decision versions of these problems in power-law graphs. In particular, we first show the NP-completeness of VERTEX-COVER for all $\beta>0$, and then we show the NP-completeness of CLIQUE and COLORING (even though the optimization versions of these two problems do not have the optimal substructure property) for $\beta\geq1$. Besides initiating a systematic study of complexity of combinatorial optimization in graphs with prescribed degree sequences, our results, in conjunction with recent experimental evidence, suggest that real-world power law graphs may not be ``worst-case'' instances of power law graphs, but rather typical instances, and may be well-modeled by power law random graph models.

Joint work with A. Ferrante and K.Park.