2026-08-15T19:37:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13312 2024-03-06T10:51:40Z ddc:004 open_access

New Algorithms for Mixed Dominating Set Dublois, Louis Lampis, Michael Paschos, Vangelis Th. FPT Algorithms Exact Algorithms Mixed Domination 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Louis Dublois and Michael Lampis and Vangelis Th. Paschos 2020 Is Part Of LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2020.9 urn:nbn:de:0030-drops-133127 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.9 eng https://creativecommons.org/licenses/by/3.0/legalcode