Parameterized approximation algorithms for some location problems in graphs

We develop efficient parameterized, with additive error, approximation algorithms for the (Connected) r-Domination problem and the (Connected) p-Center problem for unweighted and undirected graphs. Given a graphG, we show how to construct a (connected) (r+O(μ))-dominating set D with |D| ≤|D∗|efficiently. Here, D∗ is a minimum (connected) r-dominating set of G and μ is our graph parameter, which is the tree-breadth or the cluster diameter in a layering partition of G. Additionally, we show that a +O(μ)-approximation for the (Connected) p-Center problem on G can be computed in polynomial time. Our interest in these parameters stems from the fact that in many real-world networks, including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others, and in many structured classes of graphs these parameters are small constants.