Approximation Algorithms For Dominating Set Problems

Dominating set is an important field in combinatorial optimization withmany applications. Given an undirected graph G = (V,E), a set S (?) V is calleddominating set, if for each v∈V , either v∈S or v is adjacent to a vertex of S.The dominating set problem asks for a dominating set of minimum cardinality.The partial dominating set problem is to find, for a given vertex weighted graphG = (V,E;c) and a positive number K, a subset T ? V such that at least Kvertices of V are dominated by T and the total vertex weight of T is minimized.This thesis discusses the two problems from the point of view of algorithms andcomputational complexity. The main results are as follows:(1) Applying the technique of approximation algorithm for set cover problemto the dominating problem, three algorithms—greedy algorithm,primal-dual al-gorithm and LP rounding algorithm, are proposed, and further their performanceratio with theoretical approach is analyzed.(2) First a new problem, called partial dominating set problem is introduced,and show that it is in general NP-hard. Then two approximation algorithms forthis problem—the revised greedy algorithm and primal-dual algorithm based on"parameter pruning"technique, are proposed, and the proof on the performanceratio of the algorithms is given.