Complexity of the game domination problem

DOI10.1016/J.TCS.2016.07.025MaRDI QIDQ313955zbMATHOpenAlexFDO

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

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)

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 THE COMPLEXITY OF SOME COLORING GAMES
• On graphs with small game domination number
• 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 Map-Coloring Game
• The complexity of constraint satisfaction games and QCSP
• The domination game played on unions of graphs
• To satisfy impatient web surfers is hard

Cited in

(13)

• Game total domination critical graphs
• Domino Games and Complexity
• Cutting lemma and union lemma for the domination game
• Complexity of path discovery game problems
• The Game of n-Player Shove and Its Complexity
• Fractional domination game
• On graphs with largest possible game domination number
• Infinite families of circular and Möbius ladders that are total domination game critical
• On the computational complexity of the domination game
• The variety of domination games
• The game total domination problem is log-complete in PSPACE
• Complexity and monotonicity results for domination games
• An introduction to game domination in graphs

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)