A1 Refereed original research article in a scientific journal

Partition Strategies for the Maker-Breaker Domination Game




AuthorsBagan, Guillaume; Duchêne, Eric; Gledel, Valentin; Lehtilä, Tuomo; Parreau, Aline

PublisherSPRINGER

Publishing placeNEW YORK

Publication year2024

JournalAlgorithmica

Journal name in sourceALGORITHMICA

Journal acronymALGORITHMICA

Volume87

Issue2

First page 191

Last page222

Number of pages32

ISSN0178-4617

eISSN1432-0541

DOIhttps://doi.org/10.1007/s00453-024-01280-x

Web address https://doi.org/10.1007/s00453-024-01280-x

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/477381793


Abstract

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.


Last updated on 2025-27-03 at 11:41