The bottom line: a problem that is NP-hard on general graphs turns out to be solvable exactly, and reasonably fast, once you restrict attention to threshold graphs — a structured graph class that shows up in modeling hierarchical or layered networks such as certain organizational, communication, or influence structures. A new paper gives an $O(n^5)$-time algorithm for the minimum-weight version of the mixed dominating set problem on these graphs.
A dominating set is normally defined on vertices alone: pick a subset of vertices such that every vertex not in the subset is adjacent to one that is. The mixed dominating set problem generalizes this by allowing the 'dominators' to be either vertices or edges, and requiring that every vertex and every edge in the graph be dominated by something in the chosen mixed set. A vertex is dominated if it's in the set or adjacent to a vertex/incident to an edge in the set; an edge is dominated if it's in the set or shares an endpoint with something in the set. In the weighted version studied here, every vertex and edge carries a cost, and the goal is to find the mixed dominating set of least total weight — a natural stand-in for problems like placing sensors or monitors on both nodes and links of a network at minimum cost.
Formally, given a graph $G=(V,E)$ with vertex weights $w:V\to\mathbb{R}$ and edge weights $w:E\to\mathbb{R}$, the problem seeks a mixed set $D \subseteq V \cup E$ minimizing $$\sum_{x \in D} w(x)$$ subject to every $v \in V$ and every $e \in E$ being dominated by some element of $D$. Because weights can in principle be negative in some formulations, the authors first show a reduction that converts arbitrary weights into non-negative weights without changing the algorithm's asymptotic running time — a technical but necessary bit of housekeeping before the main construction can proceed.
Threshold graphs are the special structure that makes this tractable. They can be built up one vertex at a time, where each new vertex is either isolated (connected to nothing already present) or universal (connected to everything already present). That simple recursive structure is what earlier researchers have exploited to get fast algorithms for ordinary dominating set variants on threshold graphs, and it's the same lever this paper pulls for the mixed version.
The core technical move is a reduction to a problem the authors call Constrained Mixed Cover, an intermediate problem that captures the mixed-domination requirements under some extra bookkeeping constraints. They show this problem reduces to the classical minimum-weight edge-cover problem — finding a minimum-weight set of edges that touches every vertex — which is well known to be solvable in $O(n^3)$ time via existing algorithms. That reduction alone gives an efficient subroutine for a meaningful chunk of the overall problem.
Layering the threshold-graph structure and the necessary case analysis on top of that $O(n^3)$ subroutine, the authors assemble a full algorithm for minimum-weight mixed dominating set on threshold graphs that runs in $O(n^5)$ time, where $n$ is the number of vertices. That's a polynomial bound on a problem that is NP-hard for general graphs — the entire payoff of restricting to a well-structured graph class.
For a business reader, the practical upshot is narrower than it sounds: this result doesn't make mixed domination easy on arbitrary networks. It shows that if your network happens to have (or can be approximated by) the layered, nested structure of a threshold graph, an exact minimum-cost solution for combined node-and-edge monitoring or coverage problems can be computed in polynomial time rather than requiring heuristics or exponential search. That's a useful data point for anyone modeling hierarchical networks — supply chains with tiered suppliers, or communication networks with clear seniority/reach structure — where threshold-graph-like assumptions are plausible.
Sources: Author(s), 'The Minimum-Weight Mixed Dominating Set on Threshold Graphs', arXiv:2608.11057v1, http://arxiv.org/abs/2608.11057v1
