标题： 关于Grundy支配和零 forcing问题的参数化复杂性 显示英文标题

标题： On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems

摘要： 我们考虑两种不同的问题族，这些问题涉及图中的支配。 一方面，我们关注支配序列。 在这样的序列中，每个顶点支配图中未被序列中任何先前顶点支配的某个顶点。 寻找最长支配序列的问题被称为$\mathsf{Grundy~Domination}$。 根据使用闭邻域还是开邻域进行支配，该问题有另外三种版本。 我们证明，当以解的大小为参数时，这四个问题变体都是$\mathsf{W[1]}$-hard。 另一方面，我们考虑零强制问题族，这些问题是Grundy支配问题的参数化对偶。 在这些问题中，人们寻找最初被染成蓝色的最小顶点集，使得某些颜色变化规则能够将所有其他顶点染成蓝色。 Bhyravarapu 等人 [IWOCA 2025] 表明，其中一个问题，称为$\mathsf{Zero~Forcing~Set}$，当以树宽或解的大小为参数时属于$\mathsf{FPT}$。 我们将他们的树宽结果扩展到零强制的其他三种变体及其相应的Grundy支配问题。 我们的算法还意味着一个$\mathsf{FPT}$算法用于$\mathsf{Grundy~Domination}$，当以不在支配序列中的顶点数量为参数时。 显示英文摘要

摘要： 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. We show that all four problem variants are $\mathsf{W[1]}$-hard when parameterized by the solution size. On the other hand, we consider the family of Zero forcing problems which form the parameterized 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 one of these problems, 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.