{
  "annotation_id": "07e70703-631a-470f-94a4-1c64405282d6",
  "date_created": "2026-02-17T05:53:15.630000Z",
  "date_modified": "2026-02-17T05:53:15.630000Z",
  "file_hash": "741b88810d552e975239c3fc41944a99ae8e7fe9985f544e8f0b9d7dd31fc278",
  "private": false,
  "record": {
    "abstract": "Since its introduction as a Maker-Breaker positional game by Duch\\^ene et al. in 2020, the Maker-Breaker domination game has become one of the most studied positional games on vertices. In this game, two players, Dominator and Staller, alternately claim an unclaimed vertex of a given graph G. If at some point the set of vertices claimed by Dominator is a dominating set, she wins; otherwise, i.e. if Staller manages to isolate a vertex by claiming all its closed neighborhood, Staller wins.\n  Given a graph G and a first player, Dominator or Staller must have a winning strategy. We are interested in the computational complexity of determining which player has such a strategy. This problem is known to be PSPACE-complete on bipartite graphs of bounded degree and split graphs; polynomial on cographs, outerplanar graphs, and block graphs; and in NP for interval graphs.\n  In this paper, we consider the parameterized complexity of this game. We start by considering as a parameter the number of moves of both players. We prove that for the general framework of Maker-Breaker positional games in hypergraphs, determining whether Breaker can claim a transversal of the hypergraph in k moves is W[2]-complete, in contrast to the problem of determining whether Maker can claim all the vertices of a hyperedge in k moves, which is known to be W[1]-complete since 2017. These two hardness results are then applied to the Maker-Breaker domination game, proving that it is W[2]-complete to decide if Dominator can dominate the graph in k moves and W[1]-complete to decide if Staller can isolate a vertex in k moves. Next, we provide FPT algorithms for the Maker-Breaker domination game parameterized by the neighborhood diversity, the modular width, the P4-fewness, the distance to cluster, and the feedback edge number.",
    "arxiv_id": "2601.08562",
    "authors": [
      "Guillaume Bagan",
      "Mathieu Hilaire",
      "Nacim Oijid",
      "Aline Parreau"
    ],
    "categories": [
      "math.CO",
      "cs.CC",
      "cs.DM"
    ],
    "license": "http://creativecommons.org/licenses/by-nc-sa/4.0/",
    "title": "On the parameterized complexity of the Maker-Breaker domination game",
    "url": "https://arxiv.org/abs/2601.08562",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "6ac961df-33fe-4df3-b746-bab778113ee0",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}