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|≥1/2|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 (1/3−ϵ)lnn and (1/4−ϵ)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. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature.