On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems

summary

The gist

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

In short

The paper investigates Grundy domination and its dual zero forcing problems, establishing W[1]-completeness for all four Grundy variants parameterized by solution size. It also presents FPT algorithms for certain zero forcing variants based on treewidth, solving them in 2O(d^2)n time. The work shows that many related problems are solvable in XP time.

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 used across episodes

This episode discusses

The paper

On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems · Read on arXiv

Robert Scheffler

Institute of Mathematics, Brandenburg University of Technology

DOI: 10.1016/j.jcss.2026.103875

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.

More episodes

← Home