New Algorithms for Mixed Dominating Set

DOI10.46298/DMTCS.6824zbMATH Open1498.05205arXiv1911.08964OpenAlexW2991613589MaRDI QIDQ5038189

Vangelis Th. Paschos, Louis Dublois, Michael Lampis

Publication date: 30 September 2022

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

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 extsc{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^{*}(5^{tw})$ (improving the current best $O^{*}(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^{*}((2-varepsilon{)}^{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^{*}(4.172^k)$ to $O^{*}(3.510^k)$, and the best known exponential-time exact algorithm, from $O^{*}(2^n)$ and exponential space, to $O^{*}(1.912^n)$ and polynomial space.

Full work available at URL: https://arxiv.org/abs/1911.08964

zbMATH Keywords

exact algorithmsFPT algorithmsmixed domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Improved parameterized algorithms and kernels for mixed domination ⋮ On the complexity of Mixed Dominating Set

This page was built for publication: New Algorithms for Mixed Dominating Set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5038189)