TY - JOUR

T1 - Capacitated Domination

T2 - Problem Complexity and Approximation Algorithms

AU - Kao, Mong Jen

AU - Chen, Han Lin

AU - Lee, D. T.

N1 - Publisher Copyright:
© 2013, Springer Science+Business Media New York.

PY - 2015/5/1

Y1 - 2015/5/1

N2 - We consider a local service-requirement assignment problem named capacitated domination from an algorithmic point of view. In this problem, we are given a graph with three parameters defined on each vertex, which are the cost, the capacity, and the demand, of a vertex, respectively. A vertex can be chosen multiple times in order to generate sufficient capacity for the demands of the vertices in its closed neighborhood. The objective of this problem is to compute a demand assignment of minimum cost such that the demand of each vertex is fully-served by some of its closed neighbors without exceeding the amount of capacity they provide.In this paper, we provide complexity results as well as several approximation algorithms to compose a comprehensive study for this problem. First, we provide logarithmic approximations for general graphs which are asymptotically optimal. From the perspective of parameterized complexity, we show that this problem is W[1]-hard with respect to treewidth and solution size. Moreover, we show that this problem is fixed-parameter tractable with respect to treewidth and the maximum capacity of the vertices. The latter result implies a pseudo-polynomial time approximation scheme for planar graphs under a standard framework.In order to drop the pseudo-polynomial factor, we develop a constant-factor approximation for planar graphs, based on a new perspective which we call general ladders on the hierarchical structure of outer-planar graphs. We believe that the approach we use can be applicable to other capacitated covering problems.

AB - We consider a local service-requirement assignment problem named capacitated domination from an algorithmic point of view. In this problem, we are given a graph with three parameters defined on each vertex, which are the cost, the capacity, and the demand, of a vertex, respectively. A vertex can be chosen multiple times in order to generate sufficient capacity for the demands of the vertices in its closed neighborhood. The objective of this problem is to compute a demand assignment of minimum cost such that the demand of each vertex is fully-served by some of its closed neighbors without exceeding the amount of capacity they provide.In this paper, we provide complexity results as well as several approximation algorithms to compose a comprehensive study for this problem. First, we provide logarithmic approximations for general graphs which are asymptotically optimal. From the perspective of parameterized complexity, we show that this problem is W[1]-hard with respect to treewidth and solution size. Moreover, we show that this problem is fixed-parameter tractable with respect to treewidth and the maximum capacity of the vertices. The latter result implies a pseudo-polynomial time approximation scheme for planar graphs under a standard framework.In order to drop the pseudo-polynomial factor, we develop a constant-factor approximation for planar graphs, based on a new perspective which we call general ladders on the hierarchical structure of outer-planar graphs. We believe that the approach we use can be applicable to other capacitated covering problems.

KW - Approximation algorithms

KW - Capacitated domination

KW - Dominating set

KW - Graph theory

UR - http://www.scopus.com/inward/record.url?scp=84927804777&partnerID=8YFLogxK

U2 - 10.1007/s00453-013-9844-6

DO - 10.1007/s00453-013-9844-6

M3 - Article

AN - SCOPUS:84927804777

VL - 72

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 1

ER -