On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems

arXiv:2508.18104 · cs.CC, cs.DM, cs.DS, math.CO · Submitted 2025-08-25 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems".

Jane: Here's the gist of the paper. The paper investigates the parameterized complexity of Grundy domination problems and their parametric duals called zero forcing problems, showing that all four Grundy domination variants are W

1: -complete when parameterized by solution size, and providing FPT algorithms for several zero forcing variants when parameterized by treewidth or solution size <ref:2508.18104#pg5>.

Tom: Complexity of Grundy Domination Variants The authors show that all four problem variants of Grundy domination are W

1: -complete when parameterized by the solution size <ref:2508.18104#pg4>.

Jane: Specifically, they demonstrate the W

1: -completeness of a problem variant for hypergraphs as well as for the connected variants where the vertices of the dominating sequence must induce a connected subgraph <ref:2508.18104#pg5>.

Tom: The W

1: -hardness of Grundy Total Domination is established on bipartite graphs and split graphs when parameterized by the solution size <ref:2508.18104#pg4>.

Title and authors: Tom: So, to recap, the core of this paper is looking at Grundy domination and its dual zero forcing problems. They show all four Grundy variants are W one complete when parameterized by solution size.

Jane: And they also show that the dual zero forcing problems have solutions in two O of k squared times n time when parameterized by treewidth k for some cases, which is a specific structural parameter we can use instead of just the solution size.

Lu: The paper maps out all these reductions between different graph classes and problem variants on page two, showing exactly which structures lead to W one hardness and where the FPT algorithms apply.

Meng: I'm looking at that reduction section now, trying to see if the reductions from Multicolored Clique to those split graphs make sense in a practical deployment context. It just feels like a lot of graph theory jargon for a problem we’re actually trying to solve.

Lalam: Lalam here, what this summary really highlights is the connection between these domination problems and zero forcing problems being parametric duals, which is the central idea that links them together across all these complexity results on this paper.

Tom: It’s not just about saying they are hard or easy; it’s about showing how parameterizing by different things—size versus treewidth—changes the outcome completely for these domination problems and their duals.

Jane: So, the main implication is that we have a much clearer picture of where complexity lies when you switch your focus from just finding a small solution to exploiting the inherent structure of the graph.

Lu: And they also explore how these forcing set problems can be solved in XP time overall, which suggests that for many practical applications on certain graph classes, we might not need exponential time relative to the input size.

The paper's summary: Tom: The authors suggest a few key improvements or findings from their study. They focus on how they can use dynamic programming with extended versions of nice tree decompositions to solve Force R problems in two O of d squared times n time where d is the treewidth.

Jane: That means we have a concrete dynamic programming approach using tree decompositions that lets us find the smallest size of an R forcing set in two O of d squared times n time, which is a specific and useful upper bound for those instances.

Lu: And they also explore how pathwidth relates to local L sequences, showing that Connected Local L-Grundy Domination can be solved in n O of alpha G time given the graph G, which is quite good for graphs with low treewidth.

Meng: n O of alpha G time sounds good if the graph has a small independence number, but what does that mean for real-world network simulations or scheduling where we don't know the exact structure beforehand?

Lalam: Lalam here, and they also provide an extension to solve dual Grundy Total Domination and dual Local L-Grundy Domination in two O of k squared times n time when parameterized by the solution size k.

Tom: So we’ve got a solid algorithmic path now: if you know the treewidth, you can use dynamic programming for forcing sets, and if it’s local, you can use a pathwidth bound for Grundy problems.

Jane: It sounds like they're giving us concrete tools—not just theoretical hardness results—to actually build algorithms that perform better on specific types of graphs.

The paper's improvements: Tom: So to wrap up the "On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems" paper, it shows that all four Grundy domination variants are W one complete when parameterized by solution size.

Jane: And they confirm that for the zero forcing problems, they can be solved in two O of d squared times n time when parameterized by treewidth d for some cases.

Lu: The implication is that these results give us a clear map on where to look for tractability—either parameterize by solution size or by graph structure like treewidth.

Meng: For deployment, it means if your graph is bipartite or split, you should expect hardness when the solution size is small. If you can control the treewidth, we have better polynomial time solutions for many of these forcing set variants.

Lalam: Lalam here, and they also confirm that the problems are W one complete when parameterized by solution size for all of them, which means that finding a small solution is inherently hard across the board.

Tom: It's a lot to take in, but fundamentally it confirms that these domination problems are difficult when you try to find small solutions on general graphs.

Jane: And they leave open some questions about whether FPT algorithms for certain forcing set problems can be improved to linear exponents or if polynomial kernels exist for those W one hard ones.

Lu: I think the real value here is that they’ve successfully connected the different facets of these domination and forcing problems into a single, comprehensive complexity analysis.

Meng: It's valuable because it shows us exactly what breaks at scale and when we can rely on graph structure to keep things manageable instead of just hoping for a small answer.

Lalam: Lalam here, so the final picture is that the paper provides strong evidence that if you want to solve these problems, you'll either be constrained by the size of your solution or by the shape of your input graph.

Conclusion: Tom: So we've been diving into "On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems" and what it means for complexity, and basically, all four variants of Grundy domination are W one complete when you parameterize by solution size.

Jane: And they also show that the dual zero forcing problems can be solved in two O of d squared times n time when you parameterize by treewidth d for some cases.

Lu: That’s a lot of structure to unpack, and what it really changes is how we think about these problems—whether we look at the solution size or the graph's inherent shape, like its treewidth.

Meng: For deployment, that means if you have a graph with low treewidth, you can get an efficient algorithm for the forcing set problems when you parameterize by that treewidth. That’s something we could actually use to run on large datasets instead of just hoping for a small answer.

Lalam: Lalam here, and I'm very sure this result means that we have a concrete path forward for solving these forcing set problems in XP time overall, which is much better than exponential time relative to the input size.

Tom: That’s good news for scaling up things like network analysis where you need to find a certain structure efficiently.

Jane: But it also leaves open questions about whether we can get those FPT algorithms down to linear exponents or if there are polynomial kernels for the harder ones, which is something we still don't have a solid answer on.

Lu: I think the paper successfully connected the different facets of Grundy domination and zero forcing problems into one comprehensive complexity analysis, which is valuable groundwork.

Meng: It’s good to see that they’ve established exactly where the hardness lies on bipartite or split graphs when parameterized by solution size, which helps us filter what we can actually deploy.

Lalam: I'm confident that the mapping between these domination and forcing problems, as shown in this paper, is one of the most important connections we've seen lately for understanding these types of combinatorial problems.

Tom: Yeah, so even though it’s a lot of math with all those notation details about big O and n squared, the core message is that we have better tools for tackling these domination and forcing set problems depending on what constraint you choose to use.

Jane: And that's where we are going. We’ll be looking at how these structural parameters like treewidth affect things in our next segment on the show.

Robert Scheffler

Institute of Mathematics, Brandenburg University of Technology

cs.CC, cs.DM, cs.DS, math.CO

Submitted: 2025-08-25

Updated: 2026-11-13

Comments: version published in the Journal of Computer and System Sciences

Journal ref: Journal of Computer and System Sciences 164, Article 103875 (2027)

DOI: 10.1016/j.jcss.2026.103875

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 85/100

The gist: The paper investigates the parameterized complexity of Grundy domination problems and their parametric duals called zero forcing problems…

Key concepts

Grundy Domination
This problem asks for a set of vertices such that every vertex is dominated by a vertex chosen from the Grundy sequence defined by the set. It involves finding a dominating sequence based on specific ordering rules, making it complex to solve efficiently.
Zero Forcing Problems
These are the dual problems to Grundy domination. They involve selecting a set of vertices (a forcing set) that triggers a cascade of forced selections based on predefined rules. The complexity depends heavily on the structure of these rules and the graph.
W[1]-completeness
This is a complexity class used in parameterized complexity to classify problems that are likely hard to solve efficiently even when one parameter (like solution size) is small. Showing a problem is W[1]-complete means it's at the boundary of what can be solved quickly, suggesting no fast algorithm exists based on that parameter.
Treewidth
Treewidth measures how tree-like a graph is. A low treewidth indicates the graph has a simple, structured decomposition. Algorithms parameterized by treewidth often run efficiently on these structured graphs using dynamic programming approaches.

Terminology

Summary

The paper investigates the parameterized complexity of Grundy domination problems and their parametric duals called zero forcing problems, showing that all four Grundy domination variants are W[1]-complete when parameterized by solution size, and providing FPT algorithms for several zero forcing variants when parameterized by treewidth or solution size <ref:2508. p. 018104#pg5>.

Complexity of Grundy Domination Variants

The authors show that all four problem variants of Grundy domination are W[1]-complete when parameterized by the solution size <ref:2508.18104#pg4>. Specifically, they demonstrate the W[1]-completeness of a problem variant for hypergraphs as well as for the connected variants where the vertices of the dominating sequence must induce a connected subgraph <ref:2508. p. 318104#pg5>. The W[1]-hardness of Grundy Total Domination is established on bipartite graphs and split graphs when parameterized by the solution size <ref:2508. p. 918104#pg4>. Furthermore, (Connected) Grundy Domination and (Connected) Z-Grundy Domination are shown to be W[1]-hard on co-bipartite graphs when parameterized by the solution size <ref:2508. p. 318104#pg5>.

Dual Problems and Parameterization

The zero forcing problems are presented as the parametric duals of the Grundy domination problems <ref:2508.18104#pg4>. The authors show that the duals of all five Grundy domination problems can be solved in 2O(k 2)·n time when parameterized by treewidth k <ref:2508. p. 318104#pg5>. They also establish that the dual problems of L-Grundy Domination and Local L-Grundy Domination are W[1]-hard, leaving open only the parameterized complexity of the dual of Grundy Total Domination <ref:2508. p. 318104#pg5>.

Algorithmic Results for Zero Forcing Problems

The paper presents a dynamic programming approach using an extended version of nice tree-decompositions to solve Force (R) problems in 2O(d 2)·n time where d is the treewidth <ref:2508.18104#pg21>. This algorithm solves Force (R) for all non-empty rule sets R ⊆ [Z, T, D] <ref:2508.18104#pg27>. For specific cases like Force (Z) and Force (Z, D), the running time can be improved to 2O(k 2)·n time <ref:2508. p. 518104#pg34>.

Hardness Results for Zero Forcing Problems

The paper establishes W[1]-hardness results for several zero forcing problems when parameterized by solution size <ref:2508.18104#pg5>. Theorem 4.29 proves that Force (T, D) and Force (Z, T, D), along with their connected variants, are W[1]-hard on split graphs and bipartite graphs when parameterized by the solution size <ref:2508. p. 318104#pg31>. Assuming the Exponential Time Hypothesis, no f(k)n o(k) time algorithm exists for these problems even on bipartite or split graphs <ref:2508. p. 518104#pg35>.

Conclusion and Open Questions

The study concludes by showing that all these problems can be solved in 2O(d 2)·n time where d is the treewidth <ref:2508.18104#pg36>. The paper also notes that it remains open whether FPT algorithms for certain forcing set problems can be improved to linear exponents or if polynomial kernels exist for W[1]-hard problems. p. 3 The results imply that all the mentioned forcing set problems can be solved in XP time <ref:2508. p. 318104#pg34>. The paper also states that the parameterization of Force (Z, T), Force (T, D), and Force (Z, T, D) by the minimum degree δ(G) is para-NP-hard <ref:2508.18104#pg28>.

References

The paper cites numerous foundational works on domination and zero forcing problems <ref:2508.18104#pg34>. Key references include Brešar et al. p. 1 [13, 14, 15] regarding Grundy domination definitions <ref:2508. p. 518104#pg7>, Haynes et al. p. 2 [37] on Power Dominating Set <ref:2508. p. 218104#pg4>, and Bhyravarapu et al. p. 0 [7] on FPT algorithms for Zero Forcing Set <ref:2508. p. 018104#pg4>. The paper also references work on the Exponential Time Hypothesis <ref:2508. p. 518104#pg7> and results related to pathwidth bounds <ref:2508.18104#pg34>. The complexity of certain graph classes is discussed in relation to independence number bounds <ref:2508. p. 218104#pg33>. The paper also references work on the structure of forcing sets and dualities <ref:2508. p. 318104#pg5>, and algorithmic techniques like tree decompositions <ref:2508.18104#pg27>.

--- Page 36 ---

The authors provide a detailed construction for proving W[1]-hardness by reducing from Multicolored Clique to One-Sided Grundy Total Domination <ref:2508.18104#pg10> and to all the problems mentioned in Theorem 4. p. 229 <ref:2508. p. 018104#pg33>. The paper also details a complex construction for proving W[1]-hardness of Connected Local L-Grundy Domination by reducing from Multicolored Clique <ref:2508. p. 118104#pg33>. The FPT algorithm for Force (Z, T, D) and its variants is presented using a dynamic programming approach on an extended version of nice tree-decompositions <ref:2508. p. 218104#pg21>. This construction involves five node types in the tree decomposition <ref:2508. p. 418104#pg24>. The complexity analysis shows that the number of signatures is bounded by 2O(d 2)·n. p. 0 The final result provides a running time of O(d c)·2O(d 2)·n. p. 5 The paper also shows that the pathwidth is bounded by k + α(G) when a graph has a Z, T, D-forcing set of size k <ref:2508. p. 318104#pg35>.

--- Page 37 ---

The paper details the proof that Force (Z) and Force (Z, D) can be solved in 2O(k 2)·n time using Korhonen’s algorithm <ref:2508.18104#pg34>. The paper also shows that Total Force (R) and Connected Force (R) can be solved in 2O(d 2)·n time where d is the treewidth. p. 3 The authors also show that for problems on bipartite graphs and split graphs, these forcing set problems are NP-complete. p. 3 The paper provides a polynomial-time XP algorithm for all these forcing set problems. p. 4

--- Page 35 ---

The paper presents a detailed construction for proving the W[1]-hardness of Force (T, D) and Force (Z, T, D) on split graphs and bipartite graphs when parameterized by solution size <ref:2508.18104#pg33>. The reduction from Multicolored Clique to these problems is a proper FPT reduction <ref:2508. p. 9 p. 918104#pg33>. The paper concludes by showing that the problems are W[1]-complete when parameterized by solution size. p. 0 p. 0 p. 0 A key result is that (Connected) Local L-Grundy Domination can be solved in nO(α(G)) time given graph G. p. 3 The paper also shows that the problems are NP-complete on bipartite graphs and split graphs. p. 9

--- Page 32 ---

The paper provides a detailed construction for proving W[1]-hardness of Connected Local L-Grundy Domination by reducing from Multicolored Clique to all the problems mentioned in Theorem 4.29. The paper also shows that the problems are W[1]-complete when parameterized by solution size. p. 0 The final result confirms that the combination of Lemmas 4. p. 8 p. 830 and 4.36 with the fact that G' and G'' can be constructed in polynomial time shows that the given construction is a proper FPT reduction from Multicolored Clique to all the problems mentioned in Theorem 4.29. The paper concludes by showing that the problems are W[1]-complete when parameterized by solution size.

--- Page 36 ---

The authors present a detailed construction for proving W[1]-hardness of Force (T, D) and Force (Z, T, D) on split graphs and bipartite graphs when parameterized by solution size <ref:2508.18104#pg33>. The reduction from Multicolored Clique to these problems is a proper FPT reduction <ref:2508.18104#pg33>.

--- Page 36 ---

The paper shows that the problems are W[1]-complete when parameterized by solution size. The final result confirms that the combination of Lemmas 4.30 and 4.36 with the fact that G' and G'' can be constructed in polynomial time shows that the given construction is a proper FPT reduction from Multicolored Clique to all the problems mentioned in Theorem 4.29. The paper concludes by showing that the problems are W[1]-complete when parameterized by solution size.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Implementation of an FPT algorithm for Force (R) problems when parameterized by treewidth allows solving Force (R) in 2O(d 2)n time, where n is the number of vertices and d is the treewidth. This enables efficient solution finding for many forcing set variants.

  2. Development of a dynamic programming approach on extended nice tree-decompositions with signatures to solve Force (R) problems in 2O(d 2)n time, providing an algorithm that computes the smallest size of an R-forcing set.

  3. Application of the pathwidth bound relating local L-sequences to independence number allows solving Connected Local L-Grundy Domination in nO(alpha(G)) time, which is polynomial on co-bipartite graphs.

  4. Integration of a verification gadget construction for Multicolored Clique into the reduction proves W[1]-hardness for Force (Z, T, D) and its variants on split and bipartite graphs when parameterized by solution size.

  5. Extension of the algorithm to solve Dual Grundy Total Domination and Dual Local L-Grundy Domination in 2O(k 2)n time, where k is the solution size.

Sources

Related papers