Louis Dublois ; Michael Lampis ; Vangelis Th. Paschos - New Algorithms for Mixed Dominating Set

dmtcs:6824 - Discrete Mathematics & Theoretical Computer Science, April 30, 2021, vol. 23 no. 1 - https://doi.org/10.46298/dmtcs.6824
New Algorithms for Mixed Dominating SetArticle

Authors: Louis Dublois ; Michael Lampis ; Vangelis Th. Paschos

    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^*(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.

    Volume: vol. 23 no. 1
    Section: Discrete Algorithms
    Published on: April 30, 2021
    Accepted on: April 16, 2021
    Submitted on: October 5, 2020
    Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Computational Complexity

    Consultation statistics

    This page has been seen 628 times.
    This article's PDF has been downloaded 308 times.