06033165

j

06033165 Mishra, Sounaka Complexity of majority monopoly and signed domination problems. J. Discrete Algorithms 10, 49-60 (2012). 2012 Elsevier Science B.V., Amsterdam EN approximation algorithms dominating set signed domination

doi:10.1016/j.jda.2011.12.019

Summary: 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\subseteq V$ in a given graph $G=(V,E)$ such that $|N[v]\cap X|\geq\frac{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\to \{- 1,1\}$ such that $f(N[v])\geq 1$, for all $v\in V$, and the cost $f(V)=\sum_{v\in V} f(v)$ is minimized. We show that minimum majority monopoly and minimum signed domination cannot be approximated within a factor of $(\frac{1}{2}-\epsilon)$ and $(\frac{1}{3}-\epsilon)$, respectively, for any $\epsilon >0$, unless $\text{NP}\subseteq \text{Dtime}(n^{O(\log\log n)})$. 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 $\text{P}=\text{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 $\frac{4}{3}$ (asymptotically) and 1.6, respectively.