Complexity of the game domination problem

DOI10.1016/j.tcs.2016.07.025zbMath1350.68131arXiv1510.00140OpenAlexW2963136883MaRDI QIDQ313955

Gašper Košmrlj, Sandi Klavžar, Gabriel Renault, Boštjan Brešar, Paul Dorbec

Publication date: 12 September 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.00140

zbMATH Keywords

computational complexitydomination gamePOS-CNF problemPSPACE-complete problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (8)

The game total domination problem is log-complete in PSPACE ⋮ Infinite families of circular and Möbius ladders that are total domination game critical ⋮ Cutting lemma and union lemma for the domination game ⋮ On graphs with largest possible game domination number ⋮ The variety of domination games ⋮ Game total domination critical graphs ⋮ An Introduction to Game Domination in Graphs ⋮ Fractional domination game

Cites Work

• Unnamed Item
• Characterisation of forests with trivial game domination numbers
• Computing role assignments of proper interval graphs in polynomial time
• The domination game played on unions of graphs
• The complexity of constraint satisfaction games and QCSP
• On the game domination number of graphs with given minimum degree
• Domination game critical graphs
• On the complexity of some two-person perfect-information games
• Domination game played on trees and spanning subgraphs
• Domination game: effect of edge- and vertex-removal
• Reconfiguration of list \(L(2,1)\)-labelings in a graph
• Realizations of the game domination number
• To satisfy impatient web surfers is hard
• Domination game: extremal families of graphs for \(3/5\)-conjectures
• Bounded-width QBF is PSPACE-complete
• Domination game on forests
• The 3/5-conjecture for weakly \(S(K_{1, 3})\)-free forests
• Domination Game and an Imagination Strategy
• Domination Game: A proof of the $3/5$-Conjecture for Graphs with Minimum Degree at Least Two
• ON THE COMPLEXITY OF SOME COLORING GAMES
• On graphs with small game domination number
• Deciding the Winner of an Arbitrary Finite Poset Game Is PSPACE-Complete
• Extremal Problems for Game Domination Number
• The Map-Coloring Game

This page was built for publication: Complexity of the game domination problem