Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆VS⊆V, such that, for each u∈Vu∈V, |N[u]∩S|⩾|N[u]|/2|N[u]∩S|⩾|N[u]|/2 in a given graph G=(V,E)G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k  -regular graphs (k⩾5)(k⩾5), unless P=NPP=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k  -regular graphs to minimum monopoly problem for 2k2k-regular graphs and to minimum monopoly problem for (2k-1)(2k-1)-regular graphs, where k⩾3k⩾3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.