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⊆VX⊆V in a given graph G=(V,E)G=(V,E) such that |N[v]∩X|⩾12|N[v]|, for at least half of the vertices in V  . On the other hand, given a graph G=(V,E)G=(V,E), in the signed domination problem one needs to find a function f:V→{−1,1}f:V→{−1,1} such that f(N[v])⩾1f(N[v])⩾1, for all v∈Vv∈V, and the cost f(V)=∑v∈Vf(v)f(V)=∑v∈Vf(v) is minimized.We show that minimum majority monopoly and minimum signed domination cannot be approximated within a factor of (12−ϵ)lnn and (13−ϵ)lnn, respectively, for any ϵ>0ϵ>0, unless NP⊆Dtime(nO(loglogn))NP⊆Dtime(nO(loglogn)). We also prove that, if Δ is the maximum degree of a vertex in the graph, then both problems cannot be approximated within a factor of lnΔ−DlnlnΔ, for some constant D  , unless P=NPP=NP.On the positive side, we give ln(Δ+1)ln(Δ+1)-factor approximation algorithm for minimum majority monopoly problem for general graphs. We show that minimum majority monopoly problem is APXAPX-complete for graphs with degree at most 3 and at least 2 and minimum signed domination problem is APXAPX-complete, for 3-regular graphs. For 3-regular graphs, these two problems are approximable within a factor of 43 (asymptotically) and 1.6, respectively.