Cover Image

A Note on the Complexity of Defensive Domination

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chaplick, Steven, Gutowski, Grzegorz, Krawczyk, Tomasz
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Note on the Complexity of Directed Clique
by: Gutowski, Grzegorz, et al.
Published: (2026)

Modelling Network Resilience: The Complexity of Some Graph Division Games
by: Gutowski, Grzegorz, et al.
Published: (2026)

The Complexity of Drawing Graphs on Few Lines and Few Planes
by: Chaplick, Steven, et al.
Published: (2016)

Continuous Defensive Domination Problems
by: Grüne, Christoph, et al.
Published: (2026)

On the Parameterized Complexity of Semitotal Domination on Graph Classes
by: Retschmeier, Lukas
Published: (2025)

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
by: Ketkov, Sergey S., et al.
Published: (2025)

On the Complexity of Signed Roman Domination
by: Reddy, Sangam Balchandar
Published: (2025)

A Note on the Complexity of the Spectral Gap Problem
by: Yirka, Justin
Published: (2025)

The Counting General Dominating Set Framework
by: Zheng, Jiayi, et al.
Published: (2026)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

Domination in Diameter-Two Graphs and the 2-Club Cluster Vertex Deletion Parameter
by: Abu-Khzam, Faisal N., et al.
Published: (2024)

Classifying extrema using intervals
by: Gutowski, Marek W.
Published: (2006)

Dominating Set Knapsack: Profit Optimization on Dominating Sets
by: Singh, Sipra
Published: (2025)

Enumerating Minimal Defensive Alliances
by: Feng, Zhidan, et al.
Published: (2023)

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
by: Chavrimootoo, Michael C.
Published: (2024)

On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
by: Scheffler, Robert
Published: (2025)

Enumeration With Nice Roman Domination Properties
by: Mann, Kevin
Published: (2025)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

A Cautionary Note on Quantum Oracles
by: Agarwal, Avantika, et al.
Published: (2025)

A Hierarchy for Constant Communication Complexity
by: Ambainis, Andris, et al.
Published: (2025)

A Linear Kernel for Planar Vector Domination
by: Sahili, Mahabba El, et al.
Published: (2023)

Parameterized Complexity of (d,r)-Domination via Modular Decomposition
by: Cordasco, Gennaro, et al.
Published: (2024)

Computational Complexity of UAP Reverse Engineering: A Formal Analysis of Automaton Identification and Data Complexity
by: Daghbouche, Karim
Published: (2025)

Structure in Communication Complexity and Constant-Cost Complexity Classes
by: Hatami, Hamed, et al.
Published: (2024)

From Proof Complexity to Circuit Complexity via Interactive Protocols
by: Arteche, Noel, et al.
Published: (2024)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
by: Zheng, Bojin, et al.
Published: (2026)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
by: Przybyłek, Michał R., et al.
Published: (2026)

Pseudodeterministic Communication Complexity
by: Göös, Mika, et al.
Published: (2025)

The Complexity of Tensor Rank
by: Schaefer, Marcus, et al.
Published: (2016)

Query Complexity with Unknowns
by: Mande, Nikhil S., et al.
Published: (2024)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

A Parameterized-Complexity Framework for Finding Local Optima
by: Ganian, Robert, et al.
Published: (2026)

The Interplay Between Domination and Separation in Graphs
by: Chakraborty, Dipayan, et al.
Published: (2026)

Residue Domination in Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2024)

$m$-Eternal Dominating Set Problem on Subclasses of Chordal Graphs
by: Rai, Ashutosh, et al.
Published: (2026)

Random Permutations in Computational Complexity
by: Hitchcock, John M., et al.
Published: (2025)

Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)

A Strong Direct Sum Theorem for Distributional Query Complexity
by: Blanc, Guy, et al.
Published: (2024)

The Radical Solution and Computational Complexity
by: Zheng, Bojin, et al.
Published: (2024)