New Algorithms for Mixed Dominating Set

Abstract

A mixed dominating set is a collection of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for \textsc{Mixed Dominating Set}, 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^{\ast }(5^{tw})$ (improving the current best $O^{\ast }(6^{tw})$), as well as a lower bound showing that our algorithm cannot be improved under the Strong Exponential Time Hypothesis (SETH), even if parameterized by pathwidth (improving a lower bound of $O^{\ast }((2-\epsilon {)}^{pw})$). Furthermore, by using a simple but so far overlooked observation on the structure of minimal solutions, we obtain branching algorithms which improve both the best known FPT algorithm for this problem, from $O^{\ast }(4.172^k)$ to $O^{\ast }(3.510^k)$, and the best known exponential-time exact algorithm, from $O^{\ast }(2^n)$ and exponential space, to $O^{\ast }(1.912^n)$ and polynomial space.

This paper has been accepted to IPEC 2020

References in corpus (3)

• On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width
• Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center
• Optimal dynamic program for r-domination problems over tree decompositions