Approximability of open k-monopoly problems

We consider approximability of two optimization problems called Minimum Open k-Monopoly (Min-Open-k-Monopoly) and Minimum Partial Open k-Monopoly (Min-P-Open-k-Monopoly), where k is a fixed positive integer. The objective, in Min-Open-k-Monopoly, is to find a minimum cardinality vertex set S⊆V in a given graph G = (V,E) such that |N(v)∩S|≥12|N(v)|+k, for every vertex v∈V. On the other hand, given a graph G = (V,E), in Min-P-Open-k-Monopoly it is required to find a minimum cardinality vertex set S⊆ V such that |N(v)∩S|≥12|N(v)|+k, for every v∈V∖S. We prove that Min-Open-k-Monopoly and Min-P-Open-k-Monopoly are approximable within a factor of O(log n). Then, we show that these two problems cannot be approximated within a factor of (13−ε)lnn and (14−ε)lnn, respectively, for any > 0, unless NP⊆Dtime(nO(loglogn)). For 4-regular graphs, we prove that these two problems are APX-complete. Min-Open-1-Monopoly can be approximated within a factor of 2621≈1.2381 where as Min-P-Open-1-Monopoly can be approximated within a factor of 1.65153. For k ≥ 2, we also present approximation algorithms for these two problems for (2k + 2)-regular graphs.