New Algorithms for Mixed Dominating Set
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 parame...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2021-04-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/6824/pdf |
| _version_ | 1797270011180482560 |
|---|---|
| author | Louis Dublois Michael Lampis Vangelis Th. Paschos |
| author_facet | Louis Dublois Michael Lampis Vangelis Th. Paschos |
| author_sort | Louis Dublois |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:57:29Z |
| format | Article |
| id | doaj.art-7a3a566c194f409c849104a0eb42ac5b |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:29Z |
| publishDate | 2021-04-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-7a3a566c194f409c849104a0eb42ac5b2024-03-07T15:44:09ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502021-04-01vol. 23 no. 1Discrete Algorithms10.46298/dmtcs.68246824New Algorithms for Mixed Dominating SetLouis DubloisMichael LampisVangelis Th. PaschosA 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.https://dmtcs.episciences.org/6824/pdfcomputer science - data structures and algorithmscomputer science - computational complexity |
| spellingShingle | Louis Dublois Michael Lampis Vangelis Th. Paschos New Algorithms for Mixed Dominating Set Discrete Mathematics & Theoretical Computer Science computer science - data structures and algorithms computer science - computational complexity |
| title | New Algorithms for Mixed Dominating Set |
| title_full | New Algorithms for Mixed Dominating Set |
| title_fullStr | New Algorithms for Mixed Dominating Set |
| title_full_unstemmed | New Algorithms for Mixed Dominating Set |
| title_short | New Algorithms for Mixed Dominating Set |
| title_sort | new algorithms for mixed dominating set |
| topic | computer science - data structures and algorithms computer science - computational complexity |
| url | https://dmtcs.episciences.org/6824/pdf |
| work_keys_str_mv | AT louisdublois newalgorithmsformixeddominatingset AT michaellampis newalgorithmsformixeddominatingset AT vangelisthpaschos newalgorithmsformixeddominatingset |