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. We then introduce the Constrained Mixed Cover problem and reduce it to the minimum-weight edge-cover problem, obtaining an $\mathcal{O}(n^3)$-time algorithm for this subproblem, where $n$ is the number of vertices. Lastly, we obtain an $\mathcal{O}(n^5)$-time algorithm for the minimum weight mixed dominating set problem on threshold graphs.

11 pages, 2 figures