On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914511808626688 |
|---|---|
| author | Scheffler, Robert |
| author_facet | Scheffler, Robert |
| contents | We consider two different problem families that deal with domination in graphs. On the one hand, we focus on dominating sequences. In such a sequence, every vertex dominates some vertex of the graph that was not dominated by any earlier vertex in the sequence. The problem of finding the longest dominating sequence is known as $\mathsf{Grundy~Domination}$. Depending on whether the closed or the open neighborhoods are used for domination, there are three other versions of this problem: $\mathsf{Grundy~Total~Domination}$, $\mathsf{L\text{-}Grundy~Domination}$, and $\mathsf{Z\text{-}Grundy~Domination}$. We show that all four problem variants are $\mathsf{W[1]}$-complete when parameterized by the solution size.
On the other hand, we consider the family of zero forcing problems which form the parametric duals of the Grundy domination problems. In these problems, one looks for the smallest set of vertices initially colored blue such that certain color change rules are able to color all other vertices blue. Bhyravarapu et al. [IWOCA 2025] showed that the dual of $\mathsf{Z\text{-}Grundy~Domination}$, known as $\mathsf{Zero~Forcing~Set}$, is in $\mathsf{FPT}$ when parameterized by the treewidth or the solution size. We extend their treewidth result to the other three variants of zero forcing and their respective Grundy domination problems. Our algorithm also implies an $\mathsf{FPT}$ algorithm for $\mathsf{Grundy~Domination}$ when parameterized by the number of vertices that are not in the dominating sequence. In contrast, we show that $\mathsf{L\text{-}Grundy~Domination}$ is $\mathsf{W[1]}$-hard for that parameter. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18104 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems Scheffler, Robert Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics We consider two different problem families that deal with domination in graphs. On the one hand, we focus on dominating sequences. In such a sequence, every vertex dominates some vertex of the graph that was not dominated by any earlier vertex in the sequence. The problem of finding the longest dominating sequence is known as $\mathsf{Grundy~Domination}$. Depending on whether the closed or the open neighborhoods are used for domination, there are three other versions of this problem: $\mathsf{Grundy~Total~Domination}$, $\mathsf{L\text{-}Grundy~Domination}$, and $\mathsf{Z\text{-}Grundy~Domination}$. We show that all four problem variants are $\mathsf{W[1]}$-complete when parameterized by the solution size. On the other hand, we consider the family of zero forcing problems which form the parametric duals of the Grundy domination problems. In these problems, one looks for the smallest set of vertices initially colored blue such that certain color change rules are able to color all other vertices blue. Bhyravarapu et al. [IWOCA 2025] showed that the dual of $\mathsf{Z\text{-}Grundy~Domination}$, known as $\mathsf{Zero~Forcing~Set}$, is in $\mathsf{FPT}$ when parameterized by the treewidth or the solution size. We extend their treewidth result to the other three variants of zero forcing and their respective Grundy domination problems. Our algorithm also implies an $\mathsf{FPT}$ algorithm for $\mathsf{Grundy~Domination}$ when parameterized by the number of vertices that are not in the dominating sequence. In contrast, we show that $\mathsf{L\text{-}Grundy~Domination}$ is $\mathsf{W[1]}$-hard for that parameter. |
| title | On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2508.18104 |