Inapproximability of Dominating Set in Power Law Graphs
  We give logarithmic lower bounds for the approximability of the Minimum Dominating Set problem in connected (alpha,beta)-Power Law Graphs. We give also a best up to now upper approximation bound on the problem for the case of the parameters beta>2. We develop also a new functional method for proving lower approximation bounds and display a sharp phase transition between approximability and inapproximability of the underlying problem. This method could also be of independent interest. 
Mikael Gast, Mathias Hauptmann, Marek Karpinski
cs.CC cs.DM cs.DS math.CO math.OC