Parameterized Approximation Algorithms for some Location Problems in Graphs

Abstract

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 graph $G$, we show how to construct a (connected) $(r+\mathcal{O}(\mu ))$-dominating set $D$ with $|D|\le |D^{\ast }|$ efficiently. Here, $D^{\ast }$ is a minimum (connected) $r$-dominating set of $G$ and $\mu$ is our graph parameter, which is the tree-breadth or the cluster diameter in a layering partition of $G$. Additionally, we show that a $+\mathcal{O}(\mu )$-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.