Complexity of majority monopoly and signed domination problems

We consider approximability of two natural variants of classical dominating set problem, namely minimum majority monopoly and minimum signed domination. In the minimum majority monopoly problem, the objective is to find a smallest size subset X subset of V in a given graph G = (V, E) such that |N[v] boolean AND X| >= 1/2 |N[v]|, for at least half of the vertices in V. On the other hand, given a graph G = (V, E), in the signed domination problem one needs to find a function f :V -> {- 1, 1} such that f (N[v]) >= 1, for all v. V, and the cost f (V) = Sigma(v is an element of V) f (v) is minimized. We show that minimum majority monopoly and minimum signed domination cannot be approximated within a factor of (1/2 - is an element of) lnn and (1/3 - is an element of) lnn, respectively, for any is an element of > 0, unless NP subset of Dtime (n(O(loglogn))). We also prove that, if Delta is the maximum degree of a vertex in the graph, then both problems cannot be approximated within a factor of ln Delta - D ln ln Delta, for some constant D, unless P = NP. On the positive side, we give ln(Delta + 1)- factor approximation algorithm for minimum majority monopoly problem for general graphs. We show that minimum majority monopoly problem is APX-complete for graphs with degree at most 3 and at least 2 and minimum signed domination problem is APX-complete, for 3-regular graphs. For 3-regular graphs, these two problems are approximable within a factor of 4/3 (asymptotically) and 1.6, respectively. (C) 2011 Elsevier B.V. All rights reserved.