The Minimum-Weight Mixed Dominating Set on Threshold Graphs

Abstract

We study the minimum-weight mixed dominating set problem on threshold graphs. In this problem, vertices and edges have weights, and the goal is to find a mixed set of minimum total weight that dominates every vertex and edge of the graph. We first show that arbitrary weights can be reduced to non-negative weights without changing the asymptotic running time. By adapting a reduction to the minimum-weight edge cover given in Ferrarini, Kober, Lancini, and Yuditsky, we obtain an $\mathcal{O}(n^5)$-time algorithm for the minimum weight mixed dominating set problem on threshold graphs.