Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2015 Copyright 2015 Universität Bonn, Institut für Informatik, Abt. V
85352

05.02.2015

Inapproximability of Dominating Set on Power Law Graphs
(Revised Version)

Mikael Gast, Mathias Hauptmann and Marek Karpinski
[Download PostScript] [Download PDF]

We prove the first logarithmic lower bounds for the approximability of the Minimum Dominating Set problem for the case of connected (α, β)-power law graphs for α being a size parameter and β the power law exponent. We give also a best up to now upper approximation bound for this problem in the case of the parameters β > 2. We develop also a new functional method for proving lower approximation bounds and display a sharp approximation phase transition area between approximability and inapproximability of the underlying problems. Our results depend on a method which could be also of independent interest.

Last Change: 02/05/15 at 08:59:58
 English
Universität Bonn -> Institut für Informatik -> Abteilung V