کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430593 | 688056 | 2012 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Complexity of majority monopoly and signed domination problems Complexity of majority monopoly and signed domination problems](/preview/png/430593.png)
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.
Journal: Journal of Discrete Algorithms - Volume 10, January 2012, Pages 49–60