:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Grüne, Christoph, Janßen, Tom
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2605.10607
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Complexity of Graph Exploration Games
by: Fuchs, Janosch, et al.
Published: (2023)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
by: Grüne, Christoph
Published: (2022)

A Compendium of Reductions: reductions.network
by: Grüne, Christoph, et al.
Published: (2025)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
by: Grüne, Christoph, et al.
Published: (2023)

A Note on the Complexity of Defensive Domination
by: Chaplick, Steven, et al.
Published: (2025)

The Complexity of Blocking All Solutions
by: Grüne, Christoph, et al.
Published: (2025)

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
by: Grüne, Christoph, et al.
Published: (2024)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
by: Grüne, Christoph, et al.
Published: (2026)

The Complexity of Stackelberg Pricing Games
by: Grüne, Christoph, et al.
Published: (2025)

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

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
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)

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

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

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

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

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

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

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)

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

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)

On Computability of Computable Problems
by: Khaliq, Asad
Published: (2023)

The Stochastic Arrival Problem
by: Webster, Thomas
Published: (2022)

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

Hardness and Algorithmic Results for Roman \{3\}-Domination
by: Reddy, Sangam Balchandar
Published: (2025)

Fine-Grained Classification Of Detecting Dominating Patterns
by: Dransfeld, Jonathan, et al.
Published: (2025)

The Greedy Coin Change Problem
by: Gupta, Shreya, et al.
Published: (2024)

On the Hardness of the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2025)

Temporal Reachability Dominating Sets: contagion in temporal graphs
by: Kutner, David C., et al.
Published: (2023)

Parameterized Complexity of the Star Decomposition Problem
by: Hajebi, Sahab, et al.
Published: (2024)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)

Reductions Between Code Equivalence Problems
by: Cheraghchi, Mahdi, et al.
Published: (2025)

Total Search Problems in $\mathsf{ZPP}$
by: Fleming, Noah, et al.
Published: (2025)

The 2-Attractor Problem is NP-Complete
by: Fuchs, Janosch, et al.
Published: (2023)

Inverse Intersections for Boolean Satisfiability Problems
by: Homer, Paul W.
Published: (2025)

On the Exact Matching Problem in Dense Graphs
by: Maalouly, Nicolas El, et al.
Published: (2024)

Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems
by: Ghosh, Mrinalkanti
Published: (2025)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2022)