Upper and lower bounds on approximating weighted mixed domination.

A mixed dominating set of a graph G = (V , E) is a mixed set D of vertices and edges, such that for every edge or vertex, if it is not in D , then it is adjacent or incident to at least one vertex or edge in D. The mixed domination problem is to find a mixed dominating set with a minimum cardinality. It has applications in system control and some other scenarios and it is NP -hard to compute an optimal solution. This paper studies approximation algorithms and hardness of the weighted mixed dominating set problem. The weighted version is a generalization of the unweighted version, where all vertices are assigned the same nonnegative weight w v and all edges are assigned the same nonnegative weight w e , and the question is to find a mixed dominating set with a minimum total weight. Although the mixed dominating set problem has a simple 2-approximation algorithm, few approximation results for the weighted version are known. The main contributions of this paper include: 1. for w e ≥ w v , a 2-approximation algorithm; 2. for w e ≥ 2 w v , inapproximability within ratio 1.3606 unless P = N P and within ratio 2 under UGC; 3. for 2 w v > w e ≥ w v , inapproximability within ratio 1.1803 unless P = N P and within ratio 1.5 under UGC; 4. for w e < w v , inapproximability within ratio (1 − ϵ) ln ⁡ | V | unless P = N P for any ϵ > 0. [ABSTRACT FROM AUTHOR]