跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2508.18104 · v5

On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems

首次提交 2025-08-25 23:08
版本更新 2026-11-13 23:01
雷达观测 2026-11-16 11:41
arXiv ↗PDF ↗

摘要

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 Grundy Domination\mathsf{Grundy~Domination}. Depending on whether the closed or the open neighborhoods are used for domination, there are three other versions of this problem: Grundy Total Domination\mathsf{Grundy~Total~Domination}, L-Grundy Domination\mathsf{L\text{-}Grundy~Domination}, and Z-Grundy Domination\mathsf{Z\text{-}Grundy~Domination}. We show that all four problem variants are W[1]\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. It has been shown that the dual of Z-Grundy Domination\mathsf{Z\text{-}Grundy~Domination}, known as Zero Forcing Set\mathsf{Zero~Forcing~Set}, is in FPT\mathsf{FPT} when parameterized by the treewidth or the solution size. We extend the treewidth result to the other three variants of zero forcing and their respective Grundy domination problems. Our algorithm also implies an FPT\mathsf{FPT} algorithm for Grundy Domination\mathsf{Grundy~Domination} when parameterized by the number of vertices that are not in the dominating sequence. In contrast, we show that L-Grundy Domination\mathsf{L\text{-}Grundy~Domination} is W[1]\mathsf{W[1]}-hard for that parameter.

作者备注:version published in the Journal of Computer and System Sciences

期刊信息:Journal of Computer and System Sciences 164, Article 103875 (2027)

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v5,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v5 · 2026-11-13 23:01 · 最新观测版本

On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems

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 Grundy Domination\mathsf{Grundy~Domination}. Depending on whether the closed or the open neighborhoods are used for domination, there are three other versions of this problem: Grundy Total Domination\mathsf{Grundy~Total~Domination}, L-Grundy Domination\mathsf{L\text{-}Grundy~Domination}, and Z-Grundy Domination\mathsf{Z\text{-}Grundy~Domination}. We show that all four problem variants are W[1]\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. It has been shown that the dual of Z-Grundy Domination\mathsf{Z\text{-}Grundy~Domination}, known as Zero Forcing Set\mathsf{Zero~Forcing~Set}, is in FPT\mathsf{FPT} when parameterized by the treewidth or the solution size. We extend the treewidth result to the other three variants of zero forcing and their respective Grundy domination problems. Our algorithm also implies an FPT\mathsf{FPT} algorithm for Grundy Domination\mathsf{Grundy~Domination} when parameterized by the number of vertices that are not in the dominating sequence. In contrast, we show that L-Grundy Domination\mathsf{L\text{-}Grundy~Domination} is W[1]\mathsf{W[1]}-hard for that parameter.

查看此版本解读 →查看此版本原文 ↗