摘要：A mixed dominating set is a set of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for MDS, resolving some open questions. In particular, we settle the problemâs complexity parameterized by treewidth and pathwidth by giving an algorithm running in time O^*(5^{tw}) (improving the current best O^*(6^{tw})), and a lower bound showing that our algorithm cannot be improved under the SETH, even if parameterized by pathwidth (improving a lower bound of O^*((2-ε)^{pw})). Furthermore, by using a simple but so far overlooked observation on the structure of minimal solutions, we obtain branching algorithms which improve the best known FPT algorithm for this problem, from O^*(4.172^k) to O^*(3.510^k), and the best known exact algorithm, from O^*(2â¿) and exponential space, to O^*(1.912â¿) and polynomial space.
