Complexity of the game domination problem

DOI10.1016/J.TCS.2016.07.025MaRDI QIDQ313955zbMATH OpenOpenAlexFDO

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

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

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

Abstract: The game domination number is a graph invariant that arises from a game, which is related to graph domination in a similar way as the game chromatic number is related to graph coloring. In this paper we show that verifying whether the game domination number of a graph is bounded by a given integer is PSPACE-complete. This contrasts the situation of the game coloring problem whose complexity is still unknown.

Recommendations

• On the computational complexity of the domination game
• The game total domination problem is log-complete in PSPACE
• Domination games played on graphs
• Extremal problems for game domination number
• Complexity and monotonicity results for domination games

Cites work

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

Cited in

(18)

• Complexity of path discovery game problems
• 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
• Game total domination critical graphs
• The variety of domination games
• Fractional domination game
• The game total domination problem is log-complete in PSPACE
• Complexity and monotonicity results for domination games
• On the computational complexity of the domination game
• An introduction to game domination in graphs
• Domino Games and Complexity
• The Game of n-Player Shove and Its Complexity
• The normal domination game in graphs
• Complexity of the game connected domination problem
• Domination game: effect of edge contraction and edge subdivision
• Fast winning strategies for the attacker in eternal domination
• 6-uniform maker-breaker game is PSPACE-complete

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313955)