Graph marking problems show varying complexity under different rules
From FPT to W[P]: Classifying Zero Forcing, Power Domination and Their Variants
Computational ComplexityData Structures and Algorithms
Summary
Some problems involve marking nodes in a network starting from an initial set and spreading markings based on specific rules. This research studied how changing three key rules affects how hard it is to solve these problems. The authors showed that small changes can move the problem from being more easily solvable to very complex. They classified these variations along a known scale of computational difficulty called the W-hierarchy.
What this means in practice
- •For network security engineers: Design security protocols by understanding how quickly control or influence can spread through a network under varying rules.
- •For infrastructure planners: Optimize monitoring strategies in power grids by choosing marking schedules that balance complexity and coverage depending on graph features.
A theory result. No direct application yet.
Authors
Max Göttlicher, Lennard Hofmann, Christoph Niederbudde
Abstract
Zero Forcing (ZF) and Power Dominating Set (PDS) mark vertices in a graph based on a common forcing process starting from a problem-specific set of initially marked vertices. ZF initially marks the selected vertices while PDS additionally marks their neighbors. In the forcing process, a marked vertex with only one unmarked neighbor may force that neighbor which then becomes marked, too. A solution marks the entire graph by exhaustive application of this rule. One variant generalizes the forcing threshold; vertices may force when they have a fixed number of $k$ unmarked neighbors. Another variant limits propagation to a fixed number of rounds. We classify the parameterized complexity of the problem variants obtained by combining these choices of initialization, round limit and forcing threshold. We show that with appropriate choices, these variants range in parameterized complexity from fixed-parameter tractable to complete for every even layer $W[2\ell]$ of the $W$-hierarchy, and up to $W[P]$-complete. Our results demonstrate that small changes in any one of these three dimensions can lead to a sharp change in problem complexity.