arXiv preprint ·
From FPT to W[P]: Classifying Zero Forcing, Power Domination and Their Variants
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Claim-Gated Source-Risk Auditing for Generative Search
Quantum interaction can superactivate cheating under parallel repetition
A Faster Algorithm for Fewer Vertex-Disjoint Paths Parameterized by Treewidth
Complexity Barriers to State Preparation in Quantum Approximate Optimization
On Kernels and Leaves: Searching for Bare and Lush Trees
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.