Upper and lower bounds on approximating weighted mixed domination (Q5918569)

This paper studies the complexity of the weighted mixed domination problem, where all edges have a weight \(w_e>0\), and all vertices have a weight \(w_v>0\). This problem asks for a subset of vertices and edges of a graph \(G=(V,E)\) like \(D\subseteq V\cup E\) with minimal total weight where every edge or vertex not in \(D\) is either adjacent or incident to some vertex to an edge in \(D\). It is known that this problem is NP-hard. This paper extends the results by showing that \begin{itemize} \item[1.] this problem is \(2\)-approximable if \(w_e\geq w_v\) \item[2.] this problem is inapproximable within ratio 1.3606 unless \(\mathrm{P = NP}\) if \(w_e\geq 2w_v\) \item[3.] this problem is inapproximable within ratio 2 under the UGC \item[4.] this problem is inapproximable within ratio \((1- \varepsilon )\ln|V|\) unless \(\mathrm{P = NP}\) for any \(\varepsilon > 0\) if \(w_e<w_v\) \end{itemize} Note that the unweighted mixed dominating set problem has a simple 2-approximation algorithm.