A1 Refereed original research article in a scientific journal
Partition Strategies for the Maker-Breaker Domination Game
Authors: Bagan, Guillaume; Duchêne, Eric; Gledel, Valentin; Lehtilä, Tuomo; Parreau, Aline
Publisher: SPRINGER
Publishing place: NEW YORK
Publication year: 2024
Journal: Algorithmica
Journal name in source: ALGORITHMICA
Journal acronym: ALGORITHMICA
Volume: 87
Issue: 2
First page : 191
Last page: 222
Number of pages: 32
ISSN: 0178-4617
eISSN: 1432-0541
DOI: https://doi.org/10.1007/s00453-024-01280-x
Web address : https://doi.org/10.1007/s00453-024-01280-x
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/477381793
The Maker-Breaker domination game is a positional game played on a graph by two players called Dominator and Staller. The players alternately select a vertex of the graph that has not yet been chosen. Dominator wins if at some point the vertices she has chosen form a dominating set of the graph. Staller wins if Dominator cannot form a dominating set. Deciding if Dominator has a winning strategy has been shown to be a PSPACE-complete problem even when restricted to chordal or bipartite graphs. In this paper, we consider strategies for Dominator based on partitions of the graph into basic subgraphs where Dominator wins as the second player. Using partitions into cycles and edges (also called perfect [1,2]-factors), we show that Dominator always wins in regular graphs and that deciding whether Dominator has a winning strategy as a second player can be computed in polynomial time for outerplanar and block graphs. We then study partitions into subgraphs with two universal vertices, which is equivalent to considering the existence of pairing dominating sets with adjacent pairs. We show that in interval graphs, Dominator wins if and only if such a partition exists. In particular, this implies that deciding whether Dominator has a winning strategy playing second is in NP for interval graphs. We finally provide an algorithm in nk+3 for interval graphs with at most k nested intervals.
Funding information in the publication:
This research was supported by the ANR project P-GASE (ANR-21-CE48-0001-01). Tuomo Lehtilä’s research was supported by the Finnish Cultural Foundation and by the Academy of Finland grant 338797. Some parts of this research were carried out when he was in Univ Lyon, CNRS, INSA Lyon, UCBL, Centrale Lyon, Univ Lyon 2, LIRIS, UMR5205, F-69622, Villeurbanne, France and in University of Helsinki, Department of Computer Science, Helsinki, Finland.