DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.40

Maker-Maker Games of Rank 4 Are PSPACE-Complete

Authors: Florian Galliot and Jonas Sénizergues

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

The Maker-Maker convention of positional games is played on a hypergraph whose edges are interpreted as winning sets. Two players take turns picking a previously unpicked vertex, aiming at being first to pick all the vertices of some edge. Optimal play can only lead to a first player win or a draw, and deciding between the two is known to be PSPACE-complete even for 6-uniform hypergraphs. We establish PSPACE-completeness for hypergraphs of rank 4. As an intermediary, we use the recently introduced achievement positional games, a more general convention in which each player has their own winning sets (blue and red). We show that deciding whether the blue player has a winning strategy as the first player is PSPACE-complete even with blue edges of size 2 or 3 and pairwise disjoint red edges of size 2. The result for hypergraphs of rank 4 in the Maker-Maker convention follows as a simple corollary.

Cite as

Florian Galliot and Jonas Sénizergues. Maker-Maker Games of Rank 4 Are PSPACE-Complete. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{galliot_et_al:LIPIcs.STACS.2026.40,
  author =	{Galliot, Florian and S\'{e}nizergues, Jonas},
  title =	{{Maker-Maker Games of Rank 4 Are PSPACE-Complete}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.40},
  URN =		{urn:nbn:de:0030-drops-255298},
  doi =		{10.4230/LIPIcs.STACS.2026.40},
  annote =	{Keywords: Game theory, Positional games, Combinatorial games, Complexity, Hypergraphs}
}

Document

DOI: 10.4230/LIPIcs.SAND.2023.11

Making Self-Stabilizing Algorithms for Any Locally Greedy Problem

Authors: Johanne Cohen, Laurence Pilard, Mikaël Rabie, and Jonas Sénizergues

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract

Self-stabilizing algorithms are a way to deal with network dynamicity, as it will update itself after a network change (addition or removal of nodes or edges), as long as changes are not frequent. We propose an automatic transformation of synchronous distributed algorithms that solve locally greedy and mendable problems into self-stabilizing algorithms in anonymous networks. Mendable problems are a generalization of greedy problems where any partial solution may be transformed -instead of completed- into a global solution: every time we extend the partial solution, we are allowed to change the previous partial solution up to a given distance. Locally here means that to extend a solution for a node, we need to look at a constant distance from it. In order to do this, we propose the first explicit self-stabilizing algorithm computing a (k,k-1)-ruling set (i.e. a "maximal independent set at distance k"). By combining this technique multiple times, we compute a distance-K coloring of the graph. With this coloring we can finally simulate Local model algorithms running in a constant number of rounds, using the colors as unique identifiers. Our algorithms work under the Gouda daemon, similar to the probabilistic daemon: if an event should eventually happen, it will occur.

Cite as

Johanne Cohen, Laurence Pilard, Mikaël Rabie, and Jonas Sénizergues. Making Self-Stabilizing Algorithms for Any Locally Greedy Problem. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.SAND.2023.11,
  author =	{Cohen, Johanne and Pilard, Laurence and Rabie, Mika\"{e}l and S\'{e}nizergues, Jonas},
  title =	{{Making Self-Stabilizing Algorithms for Any Locally Greedy Problem}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.11},
  URN =		{urn:nbn:de:0030-drops-179475},
  doi =		{10.4230/LIPIcs.SAND.2023.11},
  annote =	{Keywords: Greedy Problem, Ruling Set, Distance-K Coloring, Self-Stabilizing Algorithm}
}

Search Results

Documents authored by Sénizergues, Jonas

Maker-Maker Games of Rank 4 Are PSPACE-Complete

Abstract

Cite as

Making Self-Stabilizing Algorithms for Any Locally Greedy Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message