On the hardness of approximating minimum monopoly problems

Abstract

We consider inapproximability for two graph optimisation problems called monopoly and partial monopoly. We prove that these problems cannot be approximated within a factor of (⅓-∈) ln n and ( ½-∈) ln n, unless NP Dtime(n^{O(log log n)}), respectively. We also show that, if Δ is the maximum degree in a graph G, then both problems cannot be approximated within a factor of ln Δ-O(ln ln Δ), unless P = NP, though both these problems can be approximated within a factor of ln(Δ) + O(1). Finally, for cubic graphs, we give a 1.6154 approximation algorithm for the monopoly problem and a 5/3 approximation algorithm for partial monopoly problem, and show that they are APX-complete.