On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
Robert Scheffler
我们考虑处理图中支配问题的两个不同问题族。一方面，我们关注支配序列。在这样的序列中，每个顶点支配图中某个未被序列中任何先前顶点支配的顶点。寻找最长支配序列的问题被称为𝖦𝗋𝗎𝗇𝖽𝗒 𝖣𝗈𝗆𝗂𝗇𝖺𝗍𝗂𝗈𝗇。根据使用闭邻域还是开邻域进行支配，该问题还有另外三个版本。我们证明，当以解的大小为参数时，所有四个问题变体都是𝖶[1]-难的。另一方面，我们考虑Zero Forcing问题族，它们构成了Grundy支配问题的参数化对偶。在这些问题中，我们寻找最小的初始着蓝色的顶点集合，使得某些颜色变化规则能够将所有其他顶点着蓝色。Bhyravarapu等人[IWOCA 2025]表明，其中一个称为𝖹𝖾𝗋𝗈 𝖥𝗈𝗋𝖼𝗂𝗇𝗀 𝖲𝖾𝗍的问题，在以树宽或解的大小为参数时属于𝖥𝖯𝖳。我们将他们的树宽结果扩展到其他三个Zero Forcing变体及其各自的Grundy支配问题。我们的算法还意味着，当以不在支配序列中的顶点数量为参数时，𝖦𝗋𝗎𝗇𝖽𝗒 𝖣𝗈𝗆𝗂𝗇𝖺𝗍𝗂𝗈𝗇存在𝖥𝖯𝖳算法。
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 𝖦𝗋𝗎𝗇𝖽𝗒 𝖣𝗈𝗆𝗂𝗇𝖺𝗍𝗂𝗈𝗇. Depending on whether the closed or the open neighborhoods are used for domination, there are three other versions of this problem. We sho...
