7 Search Results for "Rahman, Md Lutfar"

Document
DOI: 10.4230/LIPIcs.FUN.2026.5
Token Positional Games

Authors: Guillaume Bagan, Quentin Deschamps, Florian Galliot, Mirjana Mikalački, and Nacim Oijid

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
The classical Maker-Breaker positional game is played on a board which is a hypergraph ℋ, with two players, Maker and Breaker, alternately claiming vertices of ℋ until all the vertices are claimed. When the game ends, Maker wins if she has claimed all the vertices of some edge of ℋ; otherwise, Breaker wins. Playing this game in real life can be done by placing tokens on the vertices of the board. In this paper, we study the unfortunate case in which one or both players do not have enough tokens to cover all the vertices and, as such, will have to move their tokens around at some point instead of placing new ones. There may be a bias, in that Maker and Breaker do not necessarily have the same amount of tokens. The present paper initiates the study of this generalization of positional games, called token positional games. A particularly interesting case is when Maker has a winning strategy in the classical game: what is the lowest number of tokens with which she still wins against Breaker’s unlimited stock? We notably show that, for k-uniform hypergraphs on an arbitrarily large number n of vertices, this number equals k if k ∈ {2,3} but can vary from k to Ω(n) if k ≥ 4. From an algorithmic point of view, PSPACE-hardness in general is inherited from classical positional games, but we get a polynomial-time algorithm to solve the case where Breaker only has one token. We also establish EXPTIME-completeness for a "token sliding" variation of the game.
Cite as

Guillaume Bagan, Quentin Deschamps, Florian Galliot, Mirjana Mikalački, and Nacim Oijid. Token Positional Games. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bagan_et_al:LIPIcs.FUN.2026.5,
  author =	{Bagan, Guillaume and Deschamps, Quentin and Galliot, Florian and Mikala\v{c}ki, Mirjana and Oijid, Nacim},
  title =	{{Token Positional Games}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.5},
  URN =		{urn:nbn:de:0030-drops-257240},
  doi =		{10.4230/LIPIcs.FUN.2026.5},
  annote =	{Keywords: positional games, token games, hypergraphs, algorithmic complexity}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.24
On the Complexity of the Maker-Breaker Happy Vertex Game

Authors: Mathieu Hilaire, Perig Montfort, and Nacim Oijid

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
Given a c-colored graph G, a vertex v of G is said to be happy if it has the same color as all its neighbors. The notion of happy vertices was introduced by Zhang and Li [Peng Zhang and Angsheng Li, 2015] to compute the homophily of a graph. Eto, Fujimoto, Kiya, Matsushita, Miyano, Murao and Saitoh [Hiroshi Eto et al., 2025] introduced the Maker-Maker version of the Happy vertex game, where two players compete to claim more happy vertices than their opponent. We introduce here the Maker-Breaker happy vertex game: two players, Maker and Breaker, alternately color the vertices of a graph with their respective colors. Maker aims to maximize the number of happy vertices at the end, while Breaker aims to prevent her. This game is also a scoring version of the Maker-Breaker domination game introduced by Duchene, Gledel, Parreau and Renault [Duchene et al., 2020], as a happy vertex corresponds exactly to a vertex that is not dominated in the domination game. Therefore, this game is a very natural game on graphs and can be studied within the scope of scoring positional games [Bagan et al., 2024]. We initiate here the complexity study of this game, by proving that computing its score is PSPACE-complete on trees, NP-hard on caterpillars, and polynomial on subdivided stars. Finally, we provide the exact value of the score on graphs of maximum degree 2, and we provide an FPT-algorithm to compute the score on graphs of bounded neighborhood diversity. An important contribution of the paper is that, to achieve our hardness results, we introduce a new type of incidence graph called the literal-clause incidence graph for 2-SAT formulas. We prove that QMAX 2-SAT remains PSPACE-complete even if this graph is acyclic, and that MAX 2-SAT remains NP-complete, even if this graph is acyclic and has maximum degree 2, i.e. is a union of paths. We demonstrate the importance of this contribution by proving that Incidence, the scoring positional game played on a graph is also PSPACE-complete when restricted to forests.
Cite as

Mathieu Hilaire, Perig Montfort, and Nacim Oijid. On the Complexity of the Maker-Breaker Happy Vertex Game. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hilaire_et_al:LIPIcs.FUN.2026.24,
  author =	{Hilaire, Mathieu and Montfort, Perig and Oijid, Nacim},
  title =	{{On the Complexity of the Maker-Breaker Happy Vertex Game}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.24},
  URN =		{urn:nbn:de:0030-drops-257434},
  doi =		{10.4230/LIPIcs.FUN.2026.24},
  annote =	{Keywords: Maker-Breaker game, Domination game, happy vertex game, scoring game, complexity}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.89
On the Complexity of Client-Waiter and Waiter-Client Games

Authors: Valentin Gledel, Nacim Oijid, Sébastien Tavenas, and Stéphan Thomassé

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Positional games were introduced by Hales and Jewett in 1963, and their study became more popular when Erdős and Selfridge showed their connection to Ramsey theory and hypergraph coloring in 1973. Several conventions of these games exist, and the most popular one, Maker-Breaker was proved to be PSPACE-complete by Schaefer in 1978. The study of their complexity then stopped for decades, until 2017 when Bonnet, Jamain, and Saffidine proved that Maker-Breaker is W[1]-complete when parameterized by the number of moves. The study was then intensified when Rahman and Watson improved Schaefer’s result in 2021 by proving that the PSPACE-hardness holds for 6-uniform hypergraphs. More recently, Galliot, Gravier, and Sivignon proved that computing the winner on rank 3 hypergraphs is in P, and Keopke proved that the PSPACE-hardness also holds for 5-uniform hypergraphs. We focus here on the Client-Waiter and the Waiter-Client conventions. Both were proved to be NP-hard by Csernenszky, Martin, and Pluhár in 2011, but neither completeness nor positive results were known. In this paper, we complete the study of these conventions by proving that the former is PSPACE-complete, even restricted to 6-uniform hypergraphs, and by providing an FPT-algorithm for the latter, parameterized by the size of its largest edge. In particular, the winner of Waiter-Client can be computed in polynomial time in rank k hypergraphs for any fixed integer k. Finally, in search of the exact location of the complexity gap in the Client-Waiter convention, we focus on rank 3 hypergraphs. We provide an algorithm that runs in polynomial time with an oracle in NP.
Cite as

Valentin Gledel, Nacim Oijid, Sébastien Tavenas, and Stéphan Thomassé. On the Complexity of Client-Waiter and Waiter-Client Games. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 89:1-89:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gledel_et_al:LIPIcs.ICALP.2025.89,
  author =	{Gledel, Valentin and Oijid, Nacim and Tavenas, S\'{e}bastien and Thomass\'{e}, St\'{e}phan},
  title =	{{On the Complexity of Client-Waiter and Waiter-Client Games}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{89:1--89:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.89},
  URN =		{urn:nbn:de:0030-drops-234666},
  doi =		{10.4230/LIPIcs.ICALP.2025.89},
  annote =	{Keywords: Complexity, positional games, Maker-Breaker, Client-Waiter, Waiter-Client, PSPACE-complete, FPT}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.31
Erdős-Selfridge Theorem for Nonmonotone CNFs

Authors: Md Lutfar Rahman and Thomas Watson

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
In an influential paper, Erdős and Selfridge introduced the Maker-Breaker game played on a hypergraph, or equivalently, on a monotone CNF. The players take turns assigning values to variables of their choosing, and Breaker’s goal is to satisfy the CNF, while Maker’s goal is to falsify it. The Erdős-Selfridge Theorem says that the least number of clauses in any monotone CNF with k literals per clause where Maker has a winning strategy is Θ(2^k). We study the analogous question when the CNF is not necessarily monotone. We prove bounds of Θ(√2 ^k) when Maker plays last, and Ω(1.5^k) and O(r^k) when Breaker plays last, where r = (1+√5)/2≈ 1.618 is the golden ratio.
Cite as

Md Lutfar Rahman and Thomas Watson. Erdős-Selfridge Theorem for Nonmonotone CNFs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 31:1-31:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rahman_et_al:LIPIcs.SWAT.2022.31,
  author =	{Rahman, Md Lutfar and Watson, Thomas},
  title =	{{Erd\H{o}s-Selfridge Theorem for Nonmonotone CNFs}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{31:1--31:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.31},
  URN =		{urn:nbn:de:0030-drops-161916},
  doi =		{10.4230/LIPIcs.SWAT.2022.31},
  annote =	{Keywords: Game, nonmonotone, CNFs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.57
6-Uniform Maker-Breaker Game Is PSPACE-Complete

Authors: Md Lutfar Rahman and Thomas Watson

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
In a STOC 1976 paper, Schaefer proved that it is PSPACE-complete to determine the winner of the so-called Maker-Breaker game on a given set system, even when every set has size at most 11. Since then, there has been no improvement on this result. We prove that the game remains PSPACE-complete even when every set has size 6.
Cite as

Md Lutfar Rahman and Thomas Watson. 6-Uniform Maker-Breaker Game Is PSPACE-Complete. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{rahman_et_al:LIPIcs.STACS.2021.57,
  author =	{Rahman, Md Lutfar and Watson, Thomas},
  title =	{{6-Uniform Maker-Breaker Game Is PSPACE-Complete}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{57:1--57:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.57},
  URN =		{urn:nbn:de:0030-drops-137020},
  doi =		{10.4230/LIPIcs.STACS.2021.57},
  annote =	{Keywords: Game, Maker-Breaker, Complexity, Reduction, PSPACE-complete, NL-hard}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.9
Complexity of Unordered CNF Games

Authors: Md Lutfar Rahman and Thomas Watson

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study variants of this game in which the variables may be played in any order, and each turn consists of picking a remaining variable and a truth value for it. - For the version where the set of variables is partitioned into two halves and each player may only pick variables from his/her half, we prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for unbounded-width CNFs (Schaefer, STOC 1976). - For the general unordered version (where each variable can be picked by either player), we also prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for 6-CNFs (Ahlroth and Orponen, MFCS 2012) and PSPACE-complete for positive 11-CNFs (Schaefer, STOC 1976).
Cite as

Md Lutfar Rahman and Thomas Watson. Complexity of Unordered CNF Games. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{rahman_et_al:LIPIcs.ISAAC.2018.9,
  author =	{Rahman, Md Lutfar and Watson, Thomas},
  title =	{{Complexity of Unordered CNF Games}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.9},
  URN =		{urn:nbn:de:0030-drops-99574},
  doi =		{10.4230/LIPIcs.ISAAC.2018.9},
  annote =	{Keywords: CNF, Games, PSPACE-complete, SAT, Linear Time}
}
  • Refine by Type
  • 7 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 1 2025
  • 1 2022
  • 1 2021
  • 1 2018

  • Refine by Author
  • 3 Oijid, Nacim
  • 3 Rahman, Md Lutfar
  • 3 Watson, Thomas
  • 2 Galliot, Florian
  • 1 Bagan, Guillaume
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Problems, reductions and completeness
  • 2 Mathematics of computing → Hypergraphs
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 3 Complexity
  • 3 PSPACE-complete
  • 2 Game
  • 2 Maker-Breaker
  • 2 positional games
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact