On the Complexity of Client-Waiter and Waiter-Client Games

Gledel, Valentin; Oijid, Nacim; Tavenas, Sébastien; Thomassé, Stéphan

doi:10.4230/LIPIcs.ICALP.2025.89

On the Complexity of Client-Waiter and Waiter-Client Games

Valentin Gledel

Université Savoie Mont Blanc, CNRS UMR5127, LAMA, Chambéry, F-73000, France Nacim Oijid

Lebanese American University
Univ Lyon, CNRS, INSA Lyon, UCBL, Centrale Lyon, Univ Lyon 2, LIRIS, UMR5205, F-69622 Villeurbanne, France Sébastien Tavenas

Université Savoie Mont Blanc, CNRS UMR5127, LAMA, Chambéry, F-73000, France Stéphan Thomassé

Univ Lyon, EnsL, UCBL, CNRS, LIP, F-69342, LYON Cedex 07, France

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 $\mathsf{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 $\mathsf{PSPACE}$ -hardness holds for $6$ -uniform hypergraphs. More recently, Galliot, Gravier, and Sivignon proved that computing the winner on rank $3$ hypergraphs is in $\mathsf{P}$ , and Keopke proved that the $\mathsf{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 $\mathsf{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 $\mathsf{PSPACE}$ -complete, even restricted to $6$ -uniform hypergraphs, and by providing an $\mathsf{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 $\mathsf{NP}$ .

Keywords and phrases:

Complexity, positional games, Maker-Breaker, Client-Waiter, Waiter-Client, PSPACE-complete, FPT

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Combinatorial algorithms ; Mathematics of computing

\rightarrow

Hypergraphs ; Theory of computation

\rightarrow

Problems, reductions and completeness

Related Version:

Full Version: https://arxiv.org/abs/2407.06777

Funding:

This research was partly supported by the ANR project P-GASE (ANR-21-CE48-0001-01).

DOI:

10.4230/LIPIcs.ICALP.2025.89

Event:

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Editors:

Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Positional games were introduced by Hales and Jewett [24] as a generalization of the Tic-Tac-Toe game. These games are played on a hypergraph $H=(V,E)$ , on which the players alternately claim an unclaimed vertex of $V$ . Tic-Tac-Toe corresponds to the convention Maker-Maker: the first player who claims all vertices of an edge of $E$ wins. However, since the second player cannot win in Maker-Maker games, and since Maker-Maker games are not hereditary for the outcome, the study quickly switched to another convention: Maker-Breaker.

In the most studied convention, Maker-Breaker, Maker (one player) tries to claim all the vertices of an edge, while Breaker (the other player) aims to prevent her from doing so. If not explicitly specified, we assume here that Maker plays the first move. The study became more popular in 1973 when Erdős and Selfridge [15] obtained the following criterion.

Theorem 1 (Erdős-Selfridge criterion).

Let $H=(V,E)$ be a hypergraph. If

\sum_{e\in E}2^{-\lvert e\rvert}<\frac{1}{2},

then the position is a win for Breaker.

In the $(1:b)$ biased version of Maker-Breaker (where at each turn Maker selects one vertex, and then Breaker selects $b$ vertices), one can ask, for different families of hypergraphs, what is the threshold for $b$ which changes the outcome of the game. Surprisingly, for many hypergraph families (but not all), it has been found that the threshold for the random game (where both players play randomly) is essentially the same as the threshold for optimal play. This phenomenon, known as the “probabilistic intuition” was first demonstrated by Chvátal and Erdős [11], and then further developed in numerous papers, in particular by Beck (see for example the books [3] and [25]).

Schaefer proved in 1978 that it is $\mathsf{PSPACE}$ -complete to determine the winner of a Maker-Breaker game [35] (the problem appears there under the name $G_{\text{pos}}(\text{POS CNF})$ ). More precisely, he shows $\mathsf{PSPACE}$ -hardness even for hypergraphs of rank $11$ , that is when edges have size at most $11$ . A simplified proof can be found in [10]. The result was improved in 2021 by Rahman and Watson [33] and very recently by Koepke [28]: the problem is $\mathsf{PSPACE}$ -complete for $k$ -uniform hypergraphs with $k\geq 5$ (i.e., hypergraphs where all edges have size exactly $k$ ). Byskov [10] also notices that deciding the winner in a Maker-Breaker game can be reduced to the same problem in the Maker-Maker convention (up to increasing by $1$ the maximal size of its edges). In particular, deciding who wins in a Maker-Maker game is $\mathsf{PSPACE}$ -complete for $k$ -uniform hypergraphs as soon as $k\geq 7$ .

On the positive side, Kutz [29] proved in 2005 that the problem is tractable for $2$ -uniform hypergraphs and $3$ -uniform linear ones¹¹1Hypergraphs whose intersection of each pair of edges is of size at most one.. It was improved recently by Galliot, Gravier, and Sivignon [19, 20]: deciding the winner is tractable for rank $3$ hypergraphs.

Since the introduction of positional games, studies have focused on the Maker-Breaker convention. In order to have a better understanding of this convention, Beck [2] introduced the Client-Waiter and Waiter-Client conventions in 2002 under the names Chooser-Picker and Picker-Chooser. Their current names were suggested by Bednarska-Bzdȩga, Hefetz, Krivelevich and Łuczak [6] as they are less ambiguous. In both conventions, Waiter selects two vertices of the hypergraph and offers them to Client. Client then chooses one to claim, and the second one is given to Waiter. If the number of vertices is odd, the last vertex goes to Client. In the Client-Waiter convention, Client wins if she claims all vertices of an edge, otherwise Waiter wins. In the Waiter-Client convention, Waiter wins if he claims all vertices of an edge, otherwise Client wins. In the rest of the paper, Client is referred as female and Waiter as male.

Notice that these conventions can also be seen as variations of Avoider-Enforcer, the misère version of Maker-Breaker. In particular, the definition we give for Waiter-Client is the one which appears originally in Beck [2]. But since [26], Waiter-Client is often defined following the Avoider-Enforcer convention: Waiter wins if he can force Client to claim a whole edge (and if the number of vertices is odd, the last vertex goes to Waiter). One can notice that both definitions correspond in fact to the same game. Despite the fact that Maker-Breaker and Avoider-Enforcer are very different games, in this “I-cut-you’ll-choose way” paradigm, since Client picks a vertex from only two possibilities, it is symmetric to associate the chosen vertex to Client or to Waiter.

The study of Client-Waiter and Waiter-Client games was first motivated by their similarities with Maker-Breaker games. For example, Bednarska-Bzdȩga (improving previous results in [2, 12]) proved that Theorem 1 also holds in Waiter-Client convention [5]. Moreover, the “probabilistic intuition” still holds for these conventions [2]. More recently, Bednarska-Bzdȩga, Hefetz and Łuczak [7] conjectured that the value of the threshold bias in the biased Waiter-Client $H$ -game exactly matches, up to a multiplicative constant, the predictions given by a random heuristic. This conjecture has just been proved recently by Nenadov in 2023 [30]. These similarities led Beck [2] and Csernenszky, Mándity, and Pluhár [12] to conjecture that if Maker wins in a Maker-Breaker game on some hypergraph $H$ going second, then Waiter wins in Waiter-Client. Notice that up to considering the transversal of $H$ , the conjecture also implies that a win for Breaker as a second player implies a win for Waiter in the Client-Waiter game. But this conjecture was disproved by Knox [27] in 2012. Nowadays, Client-Waiter and Waiter-Client games are studied independently of Maker-Breaker games: Csernenszky [13] proved in 2010 that $7$ -in-a-row Waiter-Client is a Client win on the infinite grid, while this problem is still open in the Maker-Breaker convention, and Hefetz et al. [26] studied several classical games in Waiter-Client convention.

In terms of complexity, only few results were known about Waiter-Client and Client-Waiter games. In contrast to Maker-Breaker, Maker-Maker, Avoider-Avoider and Avoider-Enforcer, which are known to be $\mathsf{PSPACE}$ -complete [35, 10, 17, 33, 23], the asymmetry between the players moves in Waiter-Client and Client-Waiter conventions makes it more difficult to obtain reductions. In fact, Waiter has more choices than Client in his moves, which makes most reduction techniques fail. Both problems have been conjectured $\mathsf{PSPACE}$ -complete in [12]. In [14], the authors show that both problems are $\mathsf{NP}$ -hard. However, in the Waiter-Client convention, the hypergraph has an exponential number of edges but is given in a succinct way: it is the transversal of a given hypergraph. This leaves open the question of whether the problem of deciding who wins a Waiter-Client game is still $\mathsf{NP}$ -hard when the hypergraph is explicitly given via the list of its edges.

The parameterized complexity of combinatorial games emerged very early in the study of parameterized problems. Meanwhile, deep results in complexity theory were obtained using this approach. For instance, Abrahamson, Rodney, Downey, and Fellows [1] proved that $AW[3]=AW[*]$ , through the game Geography. Only few results are known on positional games with the parameterized complexity paradigm, and only related to three conventions: Maker-Breaker, Maker-Maker and Avoider-Enforcer. Their study started by Downey and Fellows, conjecturing that Short Generalized Hex was $\mathsf{FPT}$ , but it was disproved (unless $\mathsf{FPT}$ = $\mathsf{W}$ [1]) by Bonnet, Jamain and Saffidine in 2016 [9], proving its $\mathsf{W}$ [1]-hardness. Then, in 2017, Bonnet et al. [8] proved that general Maker-Breaker games are $\mathsf{W}$ [1]-complete, Avoider-Enforcer games are co- $\mathsf{W}$ [1]-complete and general Maker-Maker games are $\mathsf{AW}$ [*]-complete.

Notice that the parameterized results obtained on general positional games consider the number of moves as a parameter. This is mostly motivated by the fact that these problems are already $\mathsf{PSPACE}$ -hard for bounded rank hypergraphs. However, this is not the case in the Waiter-Client convention, and the aim of this paper is to study the complexity of determining the winner of Waiter-Client games parameterized by the rank of the hypergraph. Note that the outcome of Client-Waiter games is hereditary (see Lemma 10), but contrary to what is true for Maker-Breaker and Avoider-Enforcer games, this property does not hold anymore when the number of moves is bounded. Indeed, since Waiter can control where Client plays, the addition of isolated vertices can be used by Waiter to waste turns. Therefore, the number of moves in this convention is not as relevant as in the others.

High-level description of the results

We show that, similarly to the Maker-Breaker and Avoider-Enforcer conventions, deciding the winner of a positional game in the Client-Waiter convention is $\mathsf{PSPACE}$ -complete. The result was already conjectured in 2009 [12]. It is an improvement on [14] where the problem is shown to be $\mathsf{NP}$ -hard. Moreover, we obtain the $\mathsf{PSPACE}$ -completeness even for $6$ -uniform hypergraphs.

Theorem 2.

For $k\geq 6$ , Client-Waiter games are $\mathsf{PSPACE}$ -complete even restricted to $k$ -uniform hypergraphs.

The membership in $\mathsf{PSPACE}$ directly follows from Lemma 2.2 in [35]. So the main point is the hardness part. To prove it, we reduce the problem of deciding the winner in Client-Waiter from the problem of computing the winner in the following game.

Definition 3 ( $\mathsf{Paired\leavevmode\nobreak\ SAT}$ ).

Let $\varphi$ be a $3$ -CNF Formula over a set of pairs of variables $X=\{(x_{1},y_{1}),\dots,(x_{n},y_{n})\}$ . The $\mathsf{Paired\leavevmode\nobreak\ SAT}$ -game is played by two players, Satisfier and Falsifier as follows: while there is a variable that has not been assigned a valuation, Satisfier chooses a pair of variables $(x_{i},y_{i})$ that he has not chosen yet and gives a valuation, $\top$ or $\bot$ , to $x_{i}$ . Then Falsifier gives a valuation to $y_{i}$ . When all variables are instantiated, Satisfier wins if and only if the valuation they have provided to the $x_{i}$ s and $y_{i}$ s satisfies $\varphi$ .

The $\mathsf{Paired\leavevmode\nobreak\ SAT}$ -game is a new variant of a $\mathsf{CNF}$ -game where the play order is closer to the Client-Waiter convention: the first player chooses, at each turn, which variables she plays on and which variable the second player will have to play on.

Again, deciding who wins on this new game is $\mathsf{PSPACE}$ -complete. It is proved in the full version of the paper by a reduction from the game $3$ -QBF (known to be $\mathsf{PSPACE}$ -complete since Stockmeyer and Meyer seminal work [38]).

Theorem 4.

Deciding who is the winner of the $\mathsf{Paired\leavevmode\nobreak\ SAT}$ -game is $\mathsf{PSPACE}$ -complete.

Then Theorem 2 is obtained by reducing the $\mathsf{Paired\leavevmode\nobreak\ SAT}$ -game to the Client-Waiter one. This is done by designing a gadget (given in Figure 2) which simulates a pair of variables $(x_{i},y_{i})$ of the $\mathsf{Paired\leavevmode\nobreak\ SAT}$ -game. Notice that the reduction only creates a hypergraph of rank $6$ . But, similarly to the Maker-Breaker games [33, Corollary 4] and the Avoider-Enforcer ones [23, Lemma 7], Lemma 22 shows that the hypergraph can be turned into a $6$ -uniform one afterwards.

In the Maker-Breaker convention, as said before, it is known [33] that deciding if Maker has a winning strategy is $\mathsf{PSPACE}$ -complete over hypergraphs of rank $6$ . On the other side, the problem is easy for hypergraphs of rank 2 since Maker wins if and only if there are two adjacent $2$ -edges or the graph contains a singleton edge (result already noticed in [29]). But only recently, after a series of results [29, 32], Galliot, Gravier, and Savignon [19, 20] showed that the problem is still polynomial for hypergraphs of rank $3$ . The same question arises in the Client-Waiter convention: despite being $\mathsf{PSPACE}$ -complete over hypergraphs of rank $6$ , what can we say about the complexity of the problem for hypergraphs of low rank? For hypergraphs of rank $2$ , it is easily seen that the problem is polynomial (see Oijid’s thesis [31]). The question is already non-trivial for hypergraphs of rank $3$ .

We show that the problem of deciding if Client has a winning strategy in a rank $3$ hypergraph reduces to the problem of finding a specific structure (called a Tadpole) in a hypergraph. Tadpoles have been generalized to hypergraphs by Galliot, Gravier and Sivignon [20] to handle rank 3 Maker-Breaker games and their definitions are recalled in Definition 25. Intuitively, given $a$ and $b$ two vertices of $H$ , an $a b$ -tadpole is given by the union of a path from $a$ to $b$ and a cycle containing $b$ such that the structure is simple (two edges intersect only if they are two consecutive edges of the path or the cycle, or if one is the last edge of the path and the other an edge of the cycle containing $b$ ) and linear (the intersection of two intersecting edges is of size exactly $1$ ). More precisely, we require this structure to be $3$ -uniform, simple and linear, which means that all edges have size $3$ , the intersection of two consecutive edges has always size one, and the same vertex can not happen at two different places of the structure. An $a b$ tadpole is simply called tadpole. A tadpole is said rooted at $a$ , if it is an $a b$ -tadpole for some vertex $b$ .

We consider the problem Tadpole: Given a vertex $a$ in a $3$ -uniform hypergraph $H$ , decide if there is in $H$ a tadpole rooted at $a$ .

It is easy to check that a given subhypergraph is a tadpole, so this problem is in ${\mathsf{NP}}$ . We do not know if this problem is tractable. We note however that it would be sufficient to loop for all vertex $b$ and all triples of edges of the form $\{b,x_{1},x_{2}\},\{b,y_{1},y_{2}\},\{b,z_{1},z_{2}\}$ and check if there are two disjoint simple linear paths linking the two sources $a$ and $x_{1}$ to the targets $y_{1}$ and $z_{1}$ ( $b$ would be the contact between the path and the cycle). The complexity of the problem “Disjoint Connected Paths” for graphs has been a very fruitful research topic. In the case of two sources and two targets, the problem was shown to be tractable [37, 36]. In fact, in their well-known result, Robertson and Seymour [34] showed that the problem continues to be tractable for a constant number of sources and targets. The case where the number of sources and targets is unbounded is one of the first $\mathsf{NP}$ -complete problems in Karp’s list. For $3$ -uniform hypergraphs, it has been just proved recently [21] that the simple linear connectivity problem (one source and one target) is tractable. A corollary of the next theorem is that if the “Disjoint Connected Paths” problem for two sources and two targets is still tractable for $3$ -uniform hypergraphs, then deciding who is winning in a Client-Waiter game on a hypergraph of rank $3$ would also be tractable.

Theorem 5.

In Client-Waiter games, the problem of deciding if Client has a winning strategy for a given rank $3$ hypergraph can be solved by a polynomial time algorithm which uses the problem Tadpole as an oracle.

In particular, the problem lies in the class $\Delta_{2}^{{\mathsf{P}}}={\mathsf{P}}^{{\mathsf{NP}}}$ .

In fact, the proof of this theorem furthermore shows that the two problems are equivalent under polynomial-time Turing reductions. The problem of detecting a Tadpole can conversely be reduced to deciding on a winning position in a Client-Waiter game.

Proposition 6.

The problem Tadpole is polynomial-time many-one reducible to the problem of deciding if Client has a winning strategy in a Client-Waiter game played on a rank $3$ hypergraph.

We also focus on the second convention Waiter-Client. Surprisingly, the complexity of deciding if a position is winning is very different in this convention.

Theorem 7.

Waiter-Client is $\mathsf{FPT}$ on rank $k$ hypergraphs, parameterized by $k$ .

More precisely deciding if a hypergraph $H=(V,E)$ of rank $k$ is winning for Waiter can be decided in time $O(f(k)\lvert E\rvert\log\lvert V\rvert)$ where $f$ is a computable function, i.e., in linear time when $k$ is fixed.

This result is obtained from a structural analysis of rank $k$ hypergraphs, using the famous sunflower lemma from Erdős and Rado [16]. This is a very natural approach since, intuitively, a huge sunflower (edges pairwise intersecting on the same center set) should be “reducible” in the sense that one could replace the sunflower by a unique edge given by the center set. Indeed, if Waiter can obtain the center and the sunflower is large enough, then he can make sure to get a petal and so a set of the sunflower. This intuition should be valid, but the main difficulty is to exactly state what is “huge”, as all other potentially useful sunflowers interact. We were unable to find a simple strategy along these lines. Instead, we describe a kernelization type algorithm which produces a subset of vertices (kernel) of the hypergraph $H$ such that Waiter wins on $H$ if and only if Waiter wins on the trace of $H$ on the kernel. The argument is based on a process which ultimately reaches a fixed point, the major drawback being that the kernel size is enormously large. This kernelization provides an $\mathsf{FPT}$ algorithm for the Waiter-Client game on rank $k$ hypergraphs. This also proves that if Waiter can win, he wins using only $f(k)$ moves for some function $f$ . However, the gap between the very large upper bound and the best known lower bound ( $2^{k}-1$ moves, required to win on $2^{k}$ pairwise disjoint edges of size $k$ ) indicates how little we understand strategies in Waiter-Client games.

Nevertheless, the fact that Waiter-Client is FPT for rank $k$ hypergraphs could indicate that this convention is simpler to analyse than Maker-Breaker. It would be interesting to revisit the classical topics in which the Maker-Breaker game was tried as a tool (for instance 2-colorability of hypergraphs or the Local Lemma, see [4, 22]) to see if Waiter-Client could provide more insight.

Complexity results for the various conventions are summarized in the table below.

Table 1: Complexity in the different conventions.

Rank r	2	3	4	5	6	7+
Maker	P[Folklore]	P[19]	Open	$\mathsf{PSPACE}$ -c	$\mathsf{PSPACE}$ -c	$\mathsf{PSPACE}$ -c
-Breaker				[28]	[33]	[33, 35]
Maker	P[Folklore]	Open	Open	Open	$\mathsf{PSPACE}$ -c	$\mathsf{PSPACE}$ -c
-Maker					[28, 10]	[33, 10]
Avoider	$\mathsf{PSPACE}$ -c	$\mathsf{PSPACE}$ -c	$\mathsf{PSPACE}$ -c	$\mathsf{PSPACE}$ -c	$\mathsf{PSPACE}$ -c	$\mathsf{PSPACE}$ -c
-Avoider	[17]	[17]	[17]	[17]	[17]	[17]
Avoider	P [19]	Open	Open	Open	$\mathsf{PSPACE}$ -c	$\mathsf{PSPACE}$ -c
-Enforcer					[23]	[23]
Client	P Prop [31]	$\Delta_{2}^{{\mathsf{P}}}={\mathsf{P}}^{{\mathsf{NP}}}$	Open	Open	$\mathsf{PSPACE}$ -c	$\mathsf{PSPACE}$ -c
-Waiter		Cor 5			Thm 2	Thm 2
Waiter	P Prop 12	P Thm 7	P Thm 7	P Thm 7	P Thm 7	FPT w.r.t. $r$
-Client						Thm 7

Organization

We start with some preliminary results and definitions in Section 2. We first tackle the Waiter-Client convention in Section 3, where we prove that these games are $\mathsf{FPT}$ parameterized by the rank. We then analyze the Client-Waiter convention. We prove in Section 4 that Client-Waiter games are $\mathsf{PSPACE}$ -complete, even restricted to $6$ -uniform hypergraphs. In Section 5, we focus on rank 3 hypergraphs in Client-Waiter convention and we prove that the decision problem of determining the outcome of the game is in $\Delta_{2}^{{\mathsf{P}}}$ . For reasons of space, some of the proofs in Sections 4 and 5 are given in the full version of the paper.

2 Preliminaries

In this section, we first introduce the context of the game by providing some definitions, then we present some useful lemmas to handle Client-Waiter and Waiter-Client games.

Definition 8.

Let $H=(V,E)$ be a hypergraph and let $k$ be an integer. $H$ is said to have rank $k$ if all its edges $e\in E$ have size at most $k$ . $H$ is said to be $k$ -uniform if all its edges have size exactly $k$ .

Definition 9.

The hypergraph $H^{\prime}=(V^{\prime},E^{\prime})$ is a subhypergraph of $H=(V,E)$ if $V^{\prime}\subseteq V$ and $E^{\prime}\subseteq E$ . If $A\subseteq V$ , the induced subhypergraph $H_{|A}$ is the subhypergraph $(A,\{e\in E\mid e\subseteq A\})$ . The trace $T_{A}(H)$ of $H$ on $A$ is the hypergraph $(A,\{e\cap A\mid e\in E\})$ .

We now present some general results about Client-Waiter and Waiter-Client games. The monotonicity of Client-Waiter and Waiter-Client conventions is immediate and folkloric (it directly follows a simple strategy stealing argument): if the “Maker” player (i.e. Client in Client-Waiter and Waiter in Waiter-Client) has a winning strategy on a subhypergraph, then they have one on the general hypergraph. A proof of this lemma is available in Oijid’s thesis [31].

Lemma 10.

Let $H=(V,E)$ be a hypergraph and let $H^{\prime}=(V^{\prime},E^{\prime})$ be a subhypergraph of $H$ . If Client (resp. Waiter) wins the Client-Waiter (resp. Waiter-Client) game on $H^{\prime}$ , then Client (resp. Waiter) wins the Client-Waiter (resp. Waiter-Client) game on $H$ .

In the Client-Waiter convention, edges of size $2$ are forced moves for Waiter.

Lemma 11 (Proposition 9 from [12]).

Consider a game in the Client-Waiter convention on some hypergraph $H=(V,E)$ . Let $W,C\subset V$ be the set of vertices already claimed by Waiter and Client respectively. If there exists $e\in E$ such that $e\cap W=\emptyset$ and $|e\setminus C|=2$ , then an optimal move for Waiter is to propose the two unclaimed elements of $e$ with his next move.

3 Waiter-Client games are FPT on rank k hypergraphs

In Oijid’s thesis [31], it is proved that if Waiter can win a rank 2 Waiter-Client game, he has a winning strategy in at most three moves. This leads to the following result:

Proposition 12 (Theorem 1.70 from [31]).

Let $H=(V,E)$ be a rank $2$ hypergraph. The winner of a Waiter-Client game played on $H$ can be computed in polynomial time.

We here extend this result by proving Theorem 7, i.e., that for any $k\geq 1$ , the winner of a Waiter-Client game on a rank $k$ hypergraph can be computed in $\mathsf{FPT}$ time parameterized by $k$ . This result is a far-reaching generalization of the following easy fact: if a rank $k$ hypergraph has $2^{k}$ pairwise disjoint edges, it is Waiter’s win. In each phase, he reduces the size of the edges by one and divide their number by two, by proposing disjoint pairs of elements from different edges, preventing Client from playing in more than a half of the remaining edges.

Let $H=(V,E)$ be a rank $k$ hypergraph. We call $\ell$ -sunflower a set $S$ of $\ell\geq 1$ edges of $H$ pairwise intersecting on a fixed set $C$ called center of $S$ . When the center is empty, the sunflower simply consists of pairwise disjoint edges. We call petal of $S$ every set $s\setminus C$ where $s\in S$ . We authorize multisets in the definition, in particular, any edge $e$ of $H$ can be considered as an $\ell$ -sunflower for every $\ell\geq 1$ (the petals being the emptyset). Such a sunflower with empty petals is called trivial. The celebrated Sunflower Lemma from Erdős and Rado [16] asserts that every rank $k$ hypergraph with at least $k!(\ell-1)^{k}$ distinct edges contains a non trivial $\ell$ -sunflower. We first show that the number of inclusion-wise minimal centers is bounded in terms of $k$ and $\ell$ . This is the first step of the FPT algorithm for the Waiter-Client game.

We say that an $\ell$ -sunflower $S$ of $H$ is minimal (with respect to inclusion) if no $\ell$ -sunflower of $H$ has a center strictly included in the center of $S$ . Let $Y$ be a subset of vertices of $H$ , we say that $S$ is outside $Y$ if all petals of $S$ are disjoint from $Y$ . In particular, every edge $e\in E$ forms a trivial $\ell$ -sunflower outside $Y$ for every subset $Y\subseteq V$ .

Lemma 13.

There exists a function $mc_{k}$ for which every rank $k$ hypergraph $H$ has at most $mc_{k}(\ell)$ distinct centers of minimal $\ell$ -sunflowers. Moreover, there exists a function $omc_{k}$ such that whenever $Y$ is a subset of vertices of size $y$ , $H$ has at most $omc_{k}(\ell,y)$ distinct centers of minimal $\ell$ -sunflowers outside $Y$ .

Proof.

We focus on the existence of $mc_{k}$ , and postpone the outside case $omc_{k}$ to the end of the proof.

We just have to show that if $C_{1},\dots,C_{t}$ are distinct centers of size $c$ of a family of minimal $\ell$ -sunflowers $S_{1},\dots,S_{t}$ , then $t$ is bounded in terms of $k$ and $\ell$ . Indeed, this implies the first part of the lemma since $mc_{k}(\ell)$ will be at most $k$ times this bound. Let us fix $t^{\prime}=2k(\ell-1)+1$ . We denote by $P_{i}^{j}$ the $j^{th}$ petal of $S_{i}$ . If $t$ is large enough, we can extract a subfamily of $t^{\prime}$ sunflowers from $S_{1},\dots,S_{t}$ which, up to reordering, is assumed to be $S_{1},\dots,S_{t^{\prime}}$ with the following additional properties:

$\blacksquare$

all (distinct) centers $C_{1},\dots,C_{t^{\prime}}$ form a sunflower with center $X$ .
$\blacksquare$

for all $1\leq j\leq\ell$ , all petals $P_{1}^{j},\dots,P_{t^{\prime}}^{j}$ form a sunflower with center $Q_{j}$ .

Indeed, we just have for this to iterate $\ell+1$ extractions using the Sunflower Lemma, one for the centers, and $\ell$ for the petals. We now extract, by a simple greedy argument, an $\ell$ -sunflower $S$ centered at $X$ in $H$ . This gives a contradiction to the minimality of centers $C_{i}$ .

Let us define $B_{i}:=C_{i}\setminus X$ and $D_{i}^{j}:=P_{i}^{j}\setminus Q_{j}$ . With this notation, the $j^{th}$ edge of the sunflower $S_{i}$ is $X\cup B_{i}\cup Q_{j}\cup D_{i}^{j}$ .

Our first edge $e_{1}$ of $S$ is the first edge of $S_{1}$ , that is $C_{1}\cup P_{1}^{1}$ . Observe that $e_{1}$ intersects at most $k$ of the (pairwise disjoint) subsets $B_{i}$ and also at most $k$ of the subsets $D_{i}^{2}$ . Since $t^{\prime}>2k$ , there is an index $a$ such that $e_{1}$ is disjoint from $B_{a}\cup D_{a}^{2}$ (notice that $a$ is automatically distinct from $1$ since $e_{1}$ is disjoint of $B_{a}$ ). We pick the edge $e_{2}$ as the second edge of $S_{a}$ , that is $X\cup B_{a}\cup Q_{2}\cup D_{a}^{2}$ . Since all edges of $S_{1}$ intersect on $C_{1}$ , the edge $e_{1}$ is disjoint from $Q_{2}$ . In particular $e_{1}\cap e_{2}=X$ . By a similar argument, since $t^{\prime}>4k$ , there is an index $b$ such that $e_{1}\cup e_{2}$ is disjoint from $B_{b}\cup D_{b}^{3}$ . We now pick the edge $e_{3}$ as the third edge of $S_{b}$ . Iterating the process leads to an $\ell$ -sunflower $S$ centered at $X$ , a contradiction.

The proof for sunflowers outside some set $Y$ is similar, but we have to take care of the fact that the final sunflower $S$ must have its petals outside $Y$ . This is granted for the subsets $Q_{j}$ and $D_{i}^{j}$ , which are petals of the original $\ell$ -sunflowers $S_{1},\dots,S_{t}$ outside $Y$ . But the (pairwise disjoint) sets $B_{i}$ can intersect $Y$ . Observe that this happens at most $|Y|$ times. Hence, choosing $t^{\prime}=|Y|+2k(\ell-1)+1$ leads to a contradiction. $\hfill\blacktriangleleft$

We now turn to the key-definition. Given some integer $\ell$ , we say that a set $K\subseteq V$ is an $\ell$ -kernel of $H$ if for every edge $e\in E$ , there exists $C\subseteq e\cap K$ and an $\ell$ -sunflower $S$ outside $K$ centered at $C$ . Note that we can assume that $S$ is minimal outside $K$ . Observe that the union of all edges of $H$ is an $\ell$ -kernel for every $\ell$ , and that if $H$ has $\ell$ pairwise disjoint edges, then $\emptyset$ is an $\ell$ -kernel. We now show that there is always a bounded size kernel.

Theorem 14.

There exists a function $f_{k}$ such that every rank $k$ hypergraph $H$ has an $\ell$ -kernel of size at most $f_{k}(\ell)$ , for every integer $\ell$ .

Proof.

Let $X_{0}=\emptyset$ and $\ell$ be some integer. We denote by $C_{0}$ the set of all centers of minimal $\ell$ -sunflowers, whose size is bounded by $mc_{k}(\ell)$ by Lemma 13. We then set $X_{1}:=\bigcup C_{0}$ and start to define our sequence $(X_{i})$ as follows: Once $X_{i}$ is defined, we denote by $C_{i}$ the set of all centers of minimal $\ell$ -sunflowers outside $X_{i}$ and set $X_{i+1}:=(\bigcup C_{i})\cup X_{i}$ . Our goal is to show that there exists a step $i$ , bounded by a function on $k$ and $\ell$ , such that $X_{i+1}=X_{i}$ . Observe that when this step is reached, $X_{i}$ is an $\ell$ -kernel. Indeed, let $e\in E$ be an edge. Note that $e$ by itself is a trivial $\ell$ -sunflower outside $X_{i}$ , hence there is a $C$ included in $e$ which is the center of a minimal $\ell$ -sunflower outside $X_{i}$ . By definition of $X_{i+1}$ , we have $C\subseteq X_{i+1}=X_{i}$ , and therefore $C\subseteq X_{i}\cap e$ , implying that $X_{i}$ is an $\ell$ -kernel. To reach our conclusion, we need to show that the size of $X_{i}$ is upper bounded by some fixed function $g(i)$ (depending on $k$ and $\ell$ ). For this, we just have to bound the size of $X_{i+1}$ in terms of the size of $X_{i}$ . This is easily obtained by Lemma 13, since the total number of minimal $\ell$ -sunflowers outside $X_{i}$ is at most $omc_{k}(\ell,|X_{i}|)$ .

Let us now denote, for every $i$ , the sequence $s_{i}=(t_{0}(i),t_{1}(i),\dots,t_{k}(i))$ where $t_{c}(i)$ denotes the number of distinct centers $C$ of size $c$ of minimal $\ell$ -sunflowers outside $X_{i}$ . If $X_{i}\neq X_{i+1}$ , we claim that $s_{i+1}$ is lexicographically not larger than $s_{i}$ . To see this, assume that $c$ is minimum such that $t_{c}(i)\neq t_{c}(i+1)$ and suppose for contradiction that $t_{c}(i)<t_{c}(i+1)$ . This means that there is a set $C$ of size $c$ which is the center of a minimal $\ell$ -sunflower outside $X_{i+1}$ , but not the center of a minimal $\ell$ -sunflower outside $X_{i}$ . In particular, $C$ strictly contains $C^{\prime}$ which is the center of a minimal $\ell$ -sunflower outside $X_{i}$ , but not the center of a minimal $\ell$ -sunflower outside $X_{i+1}$ (by minimality of $C$ ). Since $t_{|C^{\prime}|}(i)=t_{|C^{\prime}|}(i+1)$ , there is a set $C^{\prime\prime}$ of size $|C^{\prime}|$ which is the center of a minimal $\ell$ -sunflower outside $X_{i+1}$ , but not the center of a minimal $\ell$ -sunflower outside $X_{i}$ . This process always finds a smaller center which is minimum outside $X_{i+1}$ but not outside $X_{i}$ . This is a contradiction.

Note that the previous argument moreover shows that if $s_{i}=s_{i+1}$ , then the centers of minimal $\ell$ -sunflowers outside $X_{i}$ and outside $X_{i+1}$ are the same, thus $X_{i}=X_{i+1}$ .

Therefore, we just have to show that the sequence $(s_{i})$ is ultimately constant after some fixed number of steps. Let us examine for this how the sequence $(s_{i})$ evolves from $i$ to $i+1$ . At each step, the minimum index coordinate $t_{c}$ which differs in $s_{i}$ and $s_{i+1}$ decreases. Meanwhile, the coordinates $t_{c^{\prime}}$ where $c^{\prime}>c$ can change in an arbitrary way, but no more than some fixed amount since the size of $X_{i+1}$ is bounded by $g(i+1)$ (a crude upper bound for the increase of $t_{c^{\prime}}$ would be for instance $omc_{k}(\ell,g(i+1))$ ). In all, this process terminates before some fixed number of steps depending on $k$ and $\ell$ . In all, since the number of minimal centers is bounded in terms of $k$ and $\ell$ , an upper bound on the number of steps can be computed as follows: when a nonzero coordinate of $s_{i}$ decreases by $1$ , all the next ones increases by at most $omc_{k}(\ell,g(i))$ . Therefore, the total increase on each coordinate can be computed inductively, and depends only on $\ell$ , $i$ – which is upperbounded by $k$ – and the maximum values of the previous coordinates which were also upperbounded by a function of $\ell$ and $k$ by induction hypothesis. Since the number of coordinates is $k+1$ , this gives an upper bound on the total number of steps depending only on $\ell$ and $k$ . $\hfill\blacktriangleleft$

Kernels are relevant for Waiter-Client games. Indeed, if $K$ is a $2^{k}$ -kernel of a rank $k$ hypergraph $H=(V,E)$ and $T_{K}(H)$ is the trace hypergraph on vertex set $K$ and edge set $E_{K}=\{e\cap K:e\in E\}$ , we have the following equivalence:

Lemma 15.

$H$ is Waiter win if and only if $T_{K}(H)$ is Waiter win.

Proof.

Since $T_{K}(H)$ is obtained by reducing the size of some edges of $H$ (and deleting isolated vertices), if Waiter has a winning strategy on $H$ , he has one on $T_{K}(H)$ .

Now assume that $T_{K}(H)$ is Waiter win. Waiter can play his strategy on $T_{K}(H)$ in order to select a set of vertices which contains some $e\cap K$ for $e\in E$ . Since $K$ is a kernel, there exists a $2^{k}$ -sunflower $S$ outside $K$ with center $C\subseteq e\cap K$ . Now Waiter just has to play outside $K$ to select one of the $2^{k}$ petals of $S$ and win the game. $\hfill\blacktriangleleft$

We can now prove Theorem 7, asserting that Waiter-Client is FPT on rank $k$ hypergraphs.

Proof.

Let $H$ be some input rank $k$ hypergraph on $n$ vertices and $m$ edges. We first describe an algorithm running in time $O(h(k)\cdot m^{2}\log(n))$ which decides if $H$ is Waiter-win.

The strategy is to compute a $2^{k}$ -kernel $K$ as in Theorem 14 which size only depends on $k$ . Then, by Lemma 15, we just have to (brute force) test in $O(BF(k))$ time if $H_{K}$ is a Waiter win. The only point to check is how efficiently one can compute the sequence $(X_{i})$ as in the proof of Theorem 14.

As the argument is similar for getting $X_{i+1}$ from $X_{i}$ , we just describe how to compute $X_{1}$ , that is the set of centers of minimal $2^{k}$ -sunflowers. An easy algorithm consists in (bottom up) testing all $2^{k}m$ subsets included in some edge of $H$ and determine which ones are centers of $2^{k}$ -sunflowers (this single test being done in linear time, see for example Lemma 9.7 in [18]). The computation of all centers can be achieved in quadratic time. Once computed, determining which centers are minimal can be done in linear time. The size of the centers and, by Lemma 13, the number of minimal centers are bounded by $k$ . Therefore by going through the list of centers (ordered by their cardinal) only a function of $k$ number of steps is required to verify if it is minimal (i.e., it suffices to check if it contains a previously computed minimal center). In all, each $X_{i}$ can be computed in quadratic time, and the number of steps is bounded in terms of $k$ .

To improve the complexity of the above algorithm to linear, we just need to show that we can output the list of the centers of the $2^{k}$ -sunflowers in linear time. First, we define a tabular $T$ of size at most $2^{k}m$ . Informally, for each $C\subseteq e\in E$ , we will store in $T[C]$ the potential elements for a $2^{k}$ -sunflower of center $C$ . So, for each edge $e\in E$ and each subset $C\subseteq e$ , $e\setminus C$ is a potential petal of a sunflower of center $C$ , and we add $e$ to $T[C]$ . Then, if $|T[C]|>k!k^{k}2^{k^{2}}$ , there is a sunflower $S$ of size $k2^{k}+1$ . But if a sunflower of center $C$ contains an edge of $S$ , it can always be replaced by another edge of $S$ . So we can safely remove from $T[C]$ one edge of $S$ . Thus, $|T[C]|$ is always bounded by $k!k^{k}2^{k^{2}}$ . Therefore, adding or removing an edge from $T[C]$ can always be done in time that only depends on $k$ . After this step, we can check for each $C$ if it is the center of a $2^{k}$ -sunflower by only considering the sets stored in $T[C]$ . $\hfill\blacktriangleleft$

4 6-uniform Client-Waiter games are PSPACE-complete

This section is dedicated to the proof of Theorem 2. As explained in the introduction, we start (in Section 4.1) with hypergraphs of rank $6$ :

Proposition 16.

Computing the winner of a Client-Waiter game is $\mathsf{PSPACE}$ -complete, even restricted to hypergraphs of rank $6$ .

We notice that the membership in $\mathsf{PSPACE}$ follows from an argument of Schaefer [35].

Lemma 17.

Both Client-Waiter and Waiter-Client positional games are in $\mathsf{PSPACE}$ .

The most classical $\mathsf{PSPACE}$ -complete problem is 3- $\mathsf{QBF}$ , the quantified version of $3$ - $\mathsf{SAT}$ . Our hardness proof is a reduction from $3$ - $\mathsf{QBF}$ , but since the roles of the players in Client-Waiter games are very different, we go through an intermediate problem $\mathsf{Paired\leavevmode\nobreak\ SAT}$ which was defined in the introduction (Definition 3). This is a variant of $3$ - $\mathsf{QBF}$ where, at each turn, Satisfier chooses an index $i$ and instantiates the variable $x_{i}$ , and then Falsifier instantiates the variable $y_{i}$ . The main idea of this game is to introduce a CNF-game mimicking the fact that one player chooses which variable the second player has to play on. We prove in the full version of the paper that solving this game is $\mathsf{PSPACE}$ -complete by a reduction from $3$ - $\mathsf{QBF}$ .

Theorem 18.

Determining the winner of the $\mathsf{Paired\leavevmode\nobreak\ SAT}$ -game is $\mathsf{PSPACE}$ -complete.

4.1 Reduction to Client-Waiter games

4.1.1 Blocks in Client-Waiter games

The main tool of several reductions of positional games is pairing strategies. However, this cannot be applied to Client-Waiter games, since only Waiter has choices about how to make the pairs. We present blocks-hypergraphs and block-strategies that will be used similarly to pairing strategies to ensure that Client can claim some vertices. A blocks-hypergraph is depicted in Figure 1. The idea of blocks was already used in the $\mathsf{NP}$ -hardness proof from [14], but we present here a more formal definition of them. Intuitively, Blocks are a generalization of Lemma 11, which are blocks of size $2$ .

Definition 19 (Blocks).

Let $H=(V,E)$ be a hypergraph. A block $B\subseteq V$ of size $2k$ is a set of vertices such that $|B|=2k$ for some $k\geq 1$ , and any set of $k+1$ vertices of $B$ is an edge.

If the vertices of $H$ can be partitioned into blocks, we say that $H$ is a blocks-hypergraph.

Figure 1: A blocks-hypergraph. The two vertices on the left form a block. The four on the right a second one. The hyperedge between them is in no block.

Lemma 20.

Let $H=(V,E)$ be a hypergraph, and let $B$ be a block of $H$ . If Waiter has a winning strategy in $H$ , he has to offer the vertices of $B$ two by two.

Proof.

Suppose that Waiter has a winning strategy in which he does not offer all vertices of $B$ two by two. Let $k=\frac{|B|}{2}$ . The first time he presents a vertex $x\in B$ with a vertex $y\notin B$ , Client can choose $x$ . Then, each time Waiter offers at least one vertex in $B$ , Client claims it. In the end, Client will claim at least $k+1$ vertices of $B$ and therefore wins. Thus, if Waiter has a winning strategy, he has to offer the vertices of $B$ two by two. $\hfill\blacktriangleleft$

Corollary 21.

Let $H=(V,E)$ be a blocks-hypergraph. If Waiter has a winning strategy in $H$ , any pair he offers contains vertices belonging to the same block of $H$ .

4.1.2 Construction of the hypergraph

We show now the reduction. The main idea of the reduction is that we construct a blocks-hypergraph, such that each block corresponds to the valuation that will be given to a variable.

Let $(\varphi,X)$ be an instance of $\mathsf{Paired\leavevmode\nobreak\ SAT}$ where $X=\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\}$ , and $\varphi=\bigwedge_{1\leq j\leq m}C_{j}$ is a 3-CNF on the variables of $X$ . We build a hypergraph $H=(V,E)$ as follows.

Let us define the set $V$ of $8n$ vertices. Let $V=\bigcup_{1\leq i\leq n}S_{i}\cup F_{i}$ , with for $1\leq i\leq n$ , $S_{i}=\{s_{i}^{0},s_{i}^{T},s_{i}^{F},s_{i}^{1}\}$ (gadget which encodes Satisfier’s choice for the variable $x_{i}$ ) and $F_{i}=\{f_{i}^{0},f_{i}^{T},f_{i}^{T^{\prime}},f_{i}^{F}\}$ (gadget which encodes Falsifier’s choice for the variable $y_{i}$ ).

Now we focus on the construction of the edges.

$\blacksquare$

The block-edges $B=\bigcup_{1\leq i\leq n}B_{i}$ , which make each $S_{i}$ and each $F_{i}$ a block:

$B_{i}=\left\{H\subseteq S_{i}\mid\lvert H\rvert=3\}\cup\{H\subseteq F_{i}\mid% \lvert H\rvert=3\right\}.$
$\blacksquare$

The pair-edges $P=\bigcup_{1\leq i\leq n}P_{i}$ (see Figure 2):

$P_{i}=\left\{\{s_{i}^{0},s_{i}^{T},f_{i}^{0},f_{i}^{T}\},\{s_{i}^{0},s_{i}^{F}% ,f_{i}^{F},f_{i}^{T}\},\{s_{i}^{0},s_{i}^{T},f_{i}^{F},f_{i}^{T^{\prime}}\},\{% s_{i}^{0},s_{i}^{F},f_{i}^{0},f_{i}^{T^{\prime}}\}\right\}.$
$\blacksquare$

The clause-edges. Each clause $C_{j}\in\varphi$ is a set of three literals $\{\ell_{j}^{1},\ell_{j}^{2},\ell_{j}^{3}\}$ . We define first, for $1\leq j\leq m$ and $k\in\{1,2,3\}$ , the set $H_{j}^{k}$ which encodes the property that the literal $\ell_{j}^{k}$ is instantiated to $\bot$ ,

$\displaystyle H_{j}^{k}=\begin{cases}\{\{s_{i}^{0},s_{i}^{T}\}\}&\text{if }% \ell_{j}^{k}=x_{i},\\ \{\{s_{i}^{0},s_{i}^{F}\}\}&\text{if }\ell_{j}^{k}=\neg x_{i},\\ \{\{f_{i}^{0},f_{i}^{T}\},\{f_{i}^{0},f_{i}^{T^{\prime}}\}\}&\text{if }\ell_{j% }^{k}=y_{i},\\ \{\{f_{i}^{F}\}\}&\text{if }\ell_{j}^{k}=\neg y_{i}.\end{cases}$

We define now the set of edges:

$C=\bigcup_{C_{j}\in\varphi}H_{j}.$

with $H_{j}=\left\{h_{1}\cup h_{2}\cup h_{3}\mid\forall k\in\{1,2,3\},\,h_{k}\in H_{% j}^{k}\right\}$

For example, if $C_{j}=x_{1}\vee y_{1}\vee\neg y_{2}$ , we have $H_{j}^{1}=\{\{s_{1}^{0},s_{1}^{T}\}\}$ , $H_{j}^{2}=\{\{f_{1}^{0},f_{1}^{T}\},\{f_{1}^{0},f_{1}^{T^{\prime}}\}\}$ and $H_{j}^{3}=\{\{f_{2}^{F}\}\}$ .
Finally, we have two edges to encode $C_{j}$ : $H_{j}=\{(s_{1}^{0},s_{1}^{T},f_{1}^{0},f_{1}^{T},f_{2}^{F}),(s_{1}^{0},s_{1}^{% T},f_{1}^{0},f_{1}^{T^{\prime}},f_{2}^{F})\}$

The gadget for the pair $(x_{i},y_{i})$ is depicted in Figure 2.

Intuitively, these edges are constructed in such a way that:

$\blacksquare$

The block-edges $B$ force Waiter to always propose two vertices in the same set.
$\blacksquare$

The pair-edges $P$ force Waiter to give to Client the choice of the value of $y_{i}$ after he has made his choice for $x_{i}$ .
$\blacksquare$

The clause-edges $C$ which represent the clauses of $\varphi$ and make the equivalence between a win of Waiter and a valuation that satisfies $\varphi$ .

Figure 2: Gadget for the vertices in

B_{i}

. A dashed set represents a block, i.e. all hyperedges of size three are present in it.

Finally, the reduction associates to the instance $(\varphi,X)$ of Paired SAT the hypergraph $H=(V,E$ ) with $E=B\cup P\cup C$ of Client-Waiter. This reduction is polynomial as $B$ contains $8n$ edges, $P$ contains $4n$ edges, and $C$ contains at most $8m$ edges (where $m$ is the number of clauses of $\varphi$ ).

We define an underlying assignment of the variables, corresponding to the moves on the hypergraph as follows:

$\blacksquare$

If Client claims $s_{i}^{T}$ , $x_{i}=\bot$
$\blacksquare$

If Client claims $s_{i}^{F}$ , $x_{i}=\top$
$\blacksquare$

If Client claims $f_{i}^{0}$ and one of $f_{i}^{T}$ , $f_{i}^{T^{\prime}}$ , $y_{i}=\bot$
$\blacksquare$

If Client claims $f_{i}^{F}$ , $y_{i}=\top$

We prove in the full version of the paper that Waiter has a winning strategy on $H$ if and only if Satisfier has a winning strategy on $\varphi$ . Then, we can obtain the proof of Proposition 16.

Proof of Proposition 16.

First, according to Lemma 17, Client-Waiter games are in $\mathsf{PSPACE}$ . We prove the hardness by a reduction from $\mathsf{Paired\leavevmode\nobreak\ SAT}$ .

Let $(\varphi,X)$ be an instance of $\mathsf{Paired\leavevmode\nobreak\ SAT}$ . Consider the hypergraph $H$ obtained from the reduction provided in Subsection 4.1.2. It has $O(|X|)$ vertices and $O(|X|+|\varphi|)$ edges, which is polynomial. Satisfier wins in $(\varphi,X)$ if and only if Waiter wins in $H$ (see full version for the details of this proof). Therefore, determining the winner of a Client-Waiter game is $\mathsf{PSPACE}$ -complete.

Moreover, as any edge of $H$ has size at most $6$ , the problem is even $\mathsf{PSPACE}$ -complete restricted to hypergraphs of rank $6$ . $\hfill\blacktriangleleft$

4.2 Reduction to 6-uniform hypergraphs

As it is done by Rahman and Watson for Maker-Breaker games [33], or by Gledel and Oijid for Avoider-Enforcer games [23], Proposition 16 can be strengthened by transforming the hypergraph of rank $6$ into a $k$ -uniform one (with $k\geq 6$ ). We achieved this with the following lemma (proved in the full version of the paper):

Lemma 22.

Let $H=(V,E)$ be a hypergraph of rank $k$ . Let $m=\min_{e\in E}(|e|)$ . If $m<k$ , there exists a hypergraph $H^{\prime}=(V^{\prime},E^{\prime})$ of rank $k$ where $\min_{e\in E^{\prime}}(|e|)=m+1$ , having $|E^{\prime}|\leq|E|+\binom{2k-2}{k}$ and $|V^{\prime}|\leq|V|+2(k-1)$ such that Client has a winning strategy in the Client-Waiter game on $H$ if and only if she has one in $H^{\prime}$ .

Hence, we obtain Theorem 2 by combining Proposition 16 and Lemma 22.

Proof.

The hypergraph obtained in the proof of Proposition 16 has rank 6. Therefore, by applying $k-1$ times Lemma 22, with $m=1,\ldots,k-1$ , we obtain a $k$ -uniform hypergraph having at most $2(k-1)^{2}$ more vertices and $(k-1)\binom{2k-2}{k}$ more edges. Thus, when $k$ is fixed, this construction is still polynomial, and the obtained hypergraph is $k$ -uniform. $\hfill\blacktriangleleft$

5 Rank 3 Client-Waiter equivalent to the problem of detecting a tadpole

Similarly to Maker-Breaker, the $\mathsf{PSPACE}$ -hardness of Client-Waiter games restricted to $6$ -uniform hypergraphs leads us to consider smaller rank hypergraphs. In this section, we prove that determining the winner for rank 3 hypergraphs is in $\Delta_{2}^{P}$ .

We show that testing if a hypergraph $H$ of rank $3$ is winning for Client reduces to the problem of searching two structures (the $a$ -snakes and the $a b$ -tadpoles) in $H$ . We start by defining them.

Definition 23.

Let $H=(V,E)$ be a hypergraph and $a,b\in V$ .

An alternating sequence of vertices and edges of $H$ , $\mathcal{P}=(x_{0},e_{1},x_{1},e_{2},\ldots,e_{t},x_{t})$ , is an $a b$ -path if $a=x_{0}$ , $b=x_{t}$ , and, for $1\leq i\leq t$ , $x_{i-1}\neq x_{i}$ and the edge $e_{i}$ contains both $x_{i-1}$ and $x_{i}$ . The number of edges $t$ is called the length of $\mathcal{P}$ . An $a$ -cycle is an $a a$ -path of length at least two. An $a b$ -path is called linear if the size of the intersection of two consecutive edges is always one. An $a$ -cycle of length at least $3$ is linear if the $a a$ -path is linear and if the intersection of the end edges is exactly $\{a\}$ . We continue to call linear an $a$ -cycle $(a,e_{1},b,e_{2},a)$ of length $2$ if $e_{1}\cap e_{2}=\{a,b\}$ . An $a b$ -path is said simple if $a$ appears only in $e_{1}$ , $b$ appears only in $e_{t}$ , and whenever some edges $e_{i}$ and $e_{j}$ intersect, then $\lvert i-j\rvert\leq 1$ . Similarly, an $a$ -cycle is simple if whenever $e_{i}$ and $e_{j}$ intersect, then $\lvert i-j\rvert\leq 1$ or $\{i,j\}=\{1,t\}$ .

An $a b$ -path is also called an $a$ -path or a path. A cycle is an $a$ -cycle for some $a$ in $V$ .

For the rest of this paper, if there is no ambiguity, we will denote paths and cycles by the set of edges in them.

Definition 24.

Let $a$ be a vertex of $H$ . An $a$ -snake is a simple linear $a$ -path $(e_{1},\ldots,e_{t})$ with $t\geq 1$ such that for all $1\leq i\leq t-1$ , $e_{i}$ has exactly size $3$ , and $e_{t}$ has size at most $2$ .

Definition 25.

Let $H=(V,E)$ be a hypergraph and $a,b\in V$ . If $a\neq b$ , an $a b$ -tadpole is a sequence of edges $T=(e_{1},\ldots,e_{s},f_{1},\ldots,f_{t})$ where:

$\blacksquare$

$a$ belongs to $e_{1}$ and no other edge;
$\blacksquare$

$b$ belongs to $e_{s}$ , $f_{1}$ , $f_{t}$ and no other edge;
$\blacksquare$

$(e_{1},\ldots,e_{s})$ is a $3$ -uniform simple linear $a b$ -path $\mathcal{P}_{T}$ ;
$\blacksquare$

$(f_{1},\ldots,f_{t})$ is a $3$ -uniform simple linear $b$ -cycle $\mathcal{C}_{T}$ ;
$\blacksquare$

$b$ is the only vertex which appears both in $\mathcal{P}_{T}$ and $\mathcal{C}_{T}$ .

If $a=b$ , an $a b$ -tadpole is just a $3$ -uniform simple linear $a$ -cycle. When $T$ is an $a b$ -tadpole, we may simply say $T$ is an $a$ -tadpole, or even just a tadpole.

Notice that the first two bullets in the definition are in fact consequences of the following ones.

We consider the problem Tadpole: Given a vertex $u$ in a $3$ -uniform hypergraph $H$ , decide if there is a $u$ -tadpole in $H$ .

We denote by $o(H)$ the outcome of an optimal Client-Waiter game on the hypergraph $H$ . We will write $o(H)=\mathcal{W}$ when Waiter has a winning strategy on $H$ , and $o(H)=\mathcal{C}$ otherwise.

Let $u$ be a vertex of $H$ , we consider the following family $u\text{-}\mathcal{F}_{H}$ of subhypergraphs of $H$ :

T\in u\text{-}\mathcal{F}_{H}\iff\begin{cases}T\text{ is a }u\text{-snake}\\ \text{or }T\text{ is a }u\text{-tadpole}.\end{cases}

Notice that $3$ -uniform simple linear $u$ -cycles are particular cases of $u$ -tadpoles, so such subhypergraphs are also in $u\text{-}\mathcal{F}_{H}$ . In the absence of ambiguity over the considered hypergraph, we will simply write $u\text{-}\mathcal{F}$ .

We notice that Waiter has a winning strategy in $H=(V,E)$ which starts by offering a pair $\{u,v\}$ if and only if Waiter has a winning strategy in both trace hypergraphs $H_{1}=T_{V\setminus\{u,v\}}(H_{|V\setminus\{u\}})$ and $H_{2}=T_{V\setminus\{u,v\}}(H_{|V\setminus\{v\}})$ . So to simplify notations, we will write $H^{+v}$ for the trace $T_{V\setminus\{v\}}(H)$ and $H^{-v}$ for the induced subhypergraph $H_{|V\setminus\{v\}}$ . In particular, we can just write $H_{1}=H^{+v-u}$ and $H_{2}=H^{+u-v}$ .

Lemma 26.

Let $u$ be a vertex of $H$ hypergraph of rank $3$ and let $T\in u\text{-}\mathcal{F}$ . Then $o(T^{+u})=\mathcal{C}$ .

Proof.

We do the proof by induction on the size (number of edges) of $T$ . By definition, each subhypergraph of $u\text{-}\mathcal{F}$ contains at least one edge.

Assume that $T$ contains exactly one edge. It means that $T$ is a $u$ -snake of length $1$ , i.e., one edge of length at most two. Since $T^{+u}$ is an edge of size at most one, it is a winning position for Client.

Assume otherwise that $T$ has at least two edges. Three cases can happen.

$\blacksquare$

$T$ is a $u$ -snake of length at least two. So $T$ is a sequence of edges of the form $(\{u,v,w\},\{v,x,y\},e_{3},\ldots,e_{\ell})$ where $e_{\ell}$ has size at most $2$ and the other edges have size $3$ . Assume $o(T^{+u})=\mathcal{W}$ , then by Lemma 11, there is a winning strategy for Waiter which starts with the pair $\{v,w\}$ . However, if Client selects $v$ , then $(\{v,x,y\},e_{3},\ldots,e_{\ell})$ is a $v$ -snake of size smaller than $T$ , and so the position is winning for Client by induction hypothesis. Hence $o(T^{+u})=\mathcal{C}$ .
$\blacksquare$

$T$ is a $3$ -uniform simple linear $u$ -cycle. So $T$ is of the form $(\{u,v,w\},\{v,x,y\},e_{3},\ldots,e_{\ell})$ where $(\{v,x,y\},e_{3},\ldots,e_{\ell})$ is a $3$ -uniform simple linear path of positive length and $e_{\ell}$ contains $u$ . The conclusion is similar to the previous case. Indeed, if in $T^{+u}$ Waiter offers the pair $\{v,w\}$ and Client picks $v$ , we obtain a $v$ -snake of size smaller than $T$ .
$\blacksquare$

$T$ is a $u$ -tadpole which is not a cycle. So $T$ is a sequence of edges of the form $(\{u,v,w\},\{v,x,y\},e_{3},\ldots,e_{\ell},e^{\prime}_{1},\ldots,e^{\prime}_{t})$ where the edge $e_{\ell}$ contains a vertex $b$ such that $(\{u,v,w\},\{v,x,y\},e_{3},\ldots,e_{\ell})$ is a $3$ -uniform simple linear $u b$ -path, and $(e^{\prime}_{1},\ldots,e^{\prime}_{t})$ is a $3$ -uniform simple linear $b$ -cycle. Assume $o(T^{+u})=\mathcal{W}$ , then by Lemma 11, there is a winning strategy for Waiter which starts with the pair $\{v,w\}$ . However, if Client selects $v$ , then $(\{v,x,y\},e_{3},\ldots,e_{\ell},e^{\prime}_{1},\ldots,e^{\prime}_{t})$ is a $v$ -tadpole of size smaller than $T$ , and so the position is winning for Client by induction hypothesis. Hence $o(T^{+u})=\mathcal{C}$ .

$\hfill\blacktriangleleft$

We show in the full version of the paper that in fact snakes and tadpoles are the only winning patterns for Client: If there are two vertices $u$ and $v$ such that $u\text{-}\mathcal{F}_{H^{-v}}$ and $v\text{-}\mathcal{F}_{H^{-u}}$ are empty, then if Waiter has a winning strategy, he has one starting by the pair $\{u,v\}$ . Consequently, testing whether a hypergraph is winning for Waiter boils down to whether such pairs can be recursively found until the hypergraph is empty.

6 Open problems

The construction of the kernel for Waiter-Client implies that, whenever Waiter has a winning strategy in a game on a hypergraph of rank $k$ , he has one with a number of moves which is bounded by a function of $k$ . We can denote by $os(k)$ the maximum number of moves needed for Waiter to win on a hypergraph of rank $k$ . Since Waiter needs $2^{k}-1$ moves to win on $2^{k}$ pairwise disjoints edges $os(k)\geq 2^{k}-1$ . Proposition 12 shows that there is equality in the case $k=2$ . However, even for $k=3$ the construction of our kernel would wield a value way larger than $2^{k}-1$ .

Problem 1: Given $k$ , what is the value of $os(k)$ ?

Theorem 5 and Proposition 6, show that the problems Tadpole and Client-Waiter for 3-uniform hypergraphs are intrinsically linked. However, as stated before, we do not know yet if the problem Tadpole is tractable, which lead us to our second problem.

Problem 2: Is Tadpole in $\mathsf{P}$ ?

Lastly, our study of Client-Waiter focused on hypergraphs of rank 6 and 3, showing that the first case is $\mathsf{PSPACE}$ -complete while the second is not. This leaves open the cases of hypergraphs of rank 4 and 5.

Problem 3: What is the complexity of Client-Waiter on hypergraphs of rank 4 and 5 ?

References

[1] Karl A. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-parameter intractability ii (extended abstract). In P. Enjalbert, A. Finkel, and K. W. Wagner, editors, STACS 93, pages 374–385, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg. doi:10.1007/3-540-56503-5_38.
[2] József Beck. Positional games and the second moment method. Combinatorica, 22:169–216, 2002. doi:10.1007/S004930200009.
[3] József Beck. Combinatorial games: tic-tac-toe theory, volume 114. Cambridge University Press Cambridge, 2008.
[4] József Beck. Surplus of Graphs and the Lovász Local Lemma, pages 47–102. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. doi:10.1007/978-3-540-85221-6_2.
[5] Małgorzata Bednarska-Bzdȩga. On weight function methods in chooser–picker games. Theoretical Computer Science, 475:21–33, 2013. doi:10.1016/J.TCS.2012.12.037.
[6] Małgorzata Bednarska-Bzdȩga, Dan Hefetz, Michael Krivelevich, and Tomasz Łuczak. Manipulative waiters with probabilistic intuition. Combinatorics, Probability and Computing, 25(6):823–849, 2016. doi:10.1017/S0963548315000310.
[7] Małgorzata Bednarska-Bzdȩga, Dan Hefetz, and Tomasz Łuczak. Picker–chooser fixed graph games. Journal of Combinatorial Theory, Series B, 119:122–154, 2016. doi:10.1016/j.jctb.2015.12.008.
[8] Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, and Abdallah Saffidine. The Parameterized Complexity of Positional Games. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 90:1–90:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2017.90.
[9] Édouard Bonnet, Florian Jamain, and Abdallah Saffidine. On the complexity of connection games. Theoretical Computer Science, 644:2–28, 2016. Recent Advances in Computer Games. doi:10.1016/j.tcs.2016.06.033.
[10] Jesper Makholm Byskov. Maker-maker and maker-breaker games are pspace-complete. BRICS Report Series, 11(14), 2004.
[11] Vašek Chvátal and Paul Erdős. Biased positional games. In Annals of Discrete Mathematics, volume 2, pages 221–229. Elsevier, 1978.
[12] András Csernenszky, C. Ivett Mándity, and András Pluhár. On chooser–picker positional games. Discrete Mathematics, 309(16):5141–5146, 2009. doi:10.1016/J.DISC.2009.03.051.
[13] András Csernenszky. The chooser-picker 7-in-a-row-game. Publicationes Mathematicae, 76, April 2010. doi:10.5486/PMD.2010.4432.
[14] András Csernenszky, Ryan Martin, and András Pluhár. On the complexity of chooser-picker positional games. Integers, 2012:427–444, November 2011. doi:10.1515/INTEG.2011.113.
[15] Paul Erdös and John L. Selfridge. On a combinatorial game. Journal of Combinatorial Theory, Series A, 14(3):298–301, 1973. doi:10.1016/0097-3165(73)90005-8.
[16] P. Erdös and R. Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, s1-35(1):85–90, 1960. doi:10.1112/jlms/s1-35.1.85.
[17] Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, and Thomas Thierauf. Game values and computational complexity: An analysis via black-white combinatorial games. In International Symposium on Algorithms and Computation, 2015. URL: https://api.semanticscholar.org/CorpusID:11815138.
[18] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer Berlin Heidelberg, 2006. URL: https://books.google.fr/books?id=VfJz6hvFAjoC.
[19] Florian Galliot. Hypergraphes et jeu Maker-Breaker : une approche structurelle. PhD thesis, Université Grenoble Alpes, 2023. Thèse de doctorat dirigée par Gravier, Sylvain et Sivignon, Isabelle Mathématiques et informatique Université Grenoble Alpes 2023. URL: http://www.theses.fr/2023GRALM028.
[20] Florian Galliot, Sylvain Gravier, and Isabelle Sivignon. Maker-breaker is solved in polynomial time on hypergraphs of rank 3. arXiv preprint arXiv:2209.12819, 2022.
[21] Florian Galliot, Sylvain Gravier, and Isabelle Sivignon. (k- 2)-linear connected components in hypergraphs of rank k. Discrete Mathematics & Theoretical Computer Science, 25(Special issues), 2023. doi:10.46298/DMTCS.10202.
[22] Heidi Gebauer. Disproof of the neighborhood conjecture with implications to sat. Combinatorica, 32:573–587, 2009. URL: https://api.semanticscholar.org/CorpusID:8773578.
[23] Valentin Gledel and Nacim Oijid. Avoidance Games Are PSPACE-Complete. In Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté, editors, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), volume 254 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:19, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2023.34.
[24] Robert I. Hales and Alfred W. Jewett. Regularity and positional games. Trans. Am. Math. Soc, 106:222–229, 1963.
[25] Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó. Positional games, volume 44. Springer, 2014.
[26] Dan Hefetz, Michael Krivelevich, and Wei En Tan. Waiter–client and client–waiter planarity, colorability and minor games. Discrete Mathematics, 339(5):1525–1536, 2016. doi:10.1016/j.disc.2015.12.020.
[27] Fiachra Knox. Two constructions relating to conjectures of beck on positional games. arXiv preprint arXiv:1212.3345, 2012.
[28] Finn Orson Koepke. Solving maker-breaker games on 5-uniform hypergraphs is pspace-complete, 2025. doi:10.48550/arXiv.2502.20271.
[29] Martin Kutz. Weak positional games on hypergraphs of rank three. Discrete Mathematics & Theoretical Computer Science, AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb ’05), 2005.
[30] Rajko Nenadov. Probabilistic intuition holds for a class of small subgraph games. Proceedings of the American Mathematical Society, 151(04):1495–1501, 2023.
[31] Nacim Oijid. Complexity of positional games on graphs. PhD thesis, Université Claude Bernard, Lyon 1, 2024. Thèse de doctorat dirigée par Duchêne, Eric et Parreau, Aline.
[32] Md Lutfar Rahman and Thomas Watson. Tractable unordered 3-cnf games. In Latin American Symposium on Theoretical Informatics, pages 360–372. Springer, 2020. doi:10.1007/978-3-030-61792-9_29.
[33] Md Lutfar Rahman and Thomas Watson. 6-uniform maker-breaker game is pspace-complete. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS), 2021.
[34] Neil Robertson and Paul D Seymour. Graph minors. xiii. the disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65–110, 1995. doi:10.1006/JCTB.1995.1006.
[35] Thomas J. Schaefer. On the Complexity of Some Two-Person Perfect-Information Games. Journal of computer and system Sciences, 16:185–225, 1978. doi:10.1016/0022-0000(78)90045-4.
[36] Paul D Seymour. Disjoint paths in graphs. Discrete mathematics, 29(3):293–309, 1980. doi:10.1016/0012-365X(80)90158-2.
[37] Yossi Shiloach. A polynomial solution to the undirected two paths problem. Journal of the ACM (JACM), 27(3):445–456, 1980. doi:10.1145/322203.322207.
[38] Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time (preliminary report). In Proceedings of the fifth annual ACM symposium on Theory of computing, pages 1–9, 1973. doi:10.1145/800125.804029.

[bib.bib1] [1] Karl A. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-parameter intractability ii (extended abstract). In P. Enjalbert, A. Finkel, and K. W. Wagner, editors, STACS 93, pages 374–385, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg. doi:10.1007/3-540-56503-5_38.

[bib.bib2] [2] József Beck. Positional games and the second moment method. Combinatorica, 22:169–216, 2002. doi:10.1007/S004930200009.

[bib.bib3] [3] József Beck. Combinatorial games: tic-tac-toe theory, volume 114. Cambridge University Press Cambridge, 2008.

[bib.bib4] [4] József Beck. Surplus of Graphs and the Lovász Local Lemma, pages 47–102. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. doi:10.1007/978-3-540-85221-6_2.

[bib.bib5] [5] Małgorzata Bednarska-Bzdȩga. On weight function methods in chooser–picker games. Theoretical Computer Science, 475:21–33, 2013. doi:10.1016/J.TCS.2012.12.037.

[bib.bib6] [6] Małgorzata Bednarska-Bzdȩga, Dan Hefetz, Michael Krivelevich, and Tomasz Łuczak. Manipulative waiters with probabilistic intuition. Combinatorics, Probability and Computing, 25(6):823–849, 2016. doi:10.1017/S0963548315000310.

[bib.bib7] [7] Małgorzata Bednarska-Bzdȩga, Dan Hefetz, and Tomasz Łuczak. Picker–chooser fixed graph games. Journal of Combinatorial Theory, Series B, 119:122–154, 2016. doi:10.1016/j.jctb.2015.12.008.

[bib.bib8] [8] Édouard Bonnet, Serge Gaspers, Antonin Lambilliotte, Stefan Rümmele, and Abdallah Saffidine. The Parameterized Complexity of Positional Games. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 90:1–90:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2017.90.

[bib.bib9] [9] Édouard Bonnet, Florian Jamain, and Abdallah Saffidine. On the complexity of connection games. Theoretical Computer Science, 644:2–28, 2016. Recent Advances in Computer Games. doi:10.1016/j.tcs.2016.06.033.

[bib.bib10] [10] Jesper Makholm Byskov. Maker-maker and maker-breaker games are pspace-complete. BRICS Report Series, 11(14), 2004.

[bib.bib11] [11] Vašek Chvátal and Paul Erdős. Biased positional games. In Annals of Discrete Mathematics, volume 2, pages 221–229. Elsevier, 1978.

[bib.bib12] [12] András Csernenszky, C. Ivett Mándity, and András Pluhár. On chooser–picker positional games. Discrete Mathematics, 309(16):5141–5146, 2009. doi:10.1016/J.DISC.2009.03.051.

[bib.bib13] [13] András Csernenszky. The chooser-picker 7-in-a-row-game. Publicationes Mathematicae, 76, April 2010. doi:10.5486/PMD.2010.4432.

[bib.bib14] [14] András Csernenszky, Ryan Martin, and András Pluhár. On the complexity of chooser-picker positional games. Integers, 2012:427–444, November 2011. doi:10.1515/INTEG.2011.113.

[bib.bib15] [15] Paul Erdös and John L. Selfridge. On a combinatorial game. Journal of Combinatorial Theory, Series A, 14(3):298–301, 1973. doi:10.1016/0097-3165(73)90005-8.

[bib.bib16] [16] P. Erdös and R. Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, s1-35(1):85–90, 1960. doi:10.1112/jlms/s1-35.1.85.

[bib.bib17] [17] Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, and Thomas Thierauf. Game values and computational complexity: An analysis via black-white combinatorial games. In International Symposium on Algorithms and Computation, 2015. URL: https://api.semanticscholar.org/CorpusID:11815138.

[bib.bib18] [18] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer Berlin Heidelberg, 2006. URL: https://books.google.fr/books?id=VfJz6hvFAjoC.

[bib.bib19] [19] Florian Galliot. Hypergraphes et jeu Maker-Breaker : une approche structurelle. PhD thesis, Université Grenoble Alpes, 2023. Thèse de doctorat dirigée par Gravier, Sylvain et Sivignon, Isabelle Mathématiques et informatique Université Grenoble Alpes 2023. URL: http://www.theses.fr/2023GRALM028.

[bib.bib20] [20] Florian Galliot, Sylvain Gravier, and Isabelle Sivignon. Maker-breaker is solved in polynomial time on hypergraphs of rank 3. arXiv preprint arXiv:2209.12819, 2022.

[bib.bib21] [21] Florian Galliot, Sylvain Gravier, and Isabelle Sivignon. (k- 2)-linear connected components in hypergraphs of rank k. Discrete Mathematics & Theoretical Computer Science, 25(Special issues), 2023. doi:10.46298/DMTCS.10202.

[bib.bib22] [22] Heidi Gebauer. Disproof of the neighborhood conjecture with implications to sat. Combinatorica, 32:573–587, 2009. URL: https://api.semanticscholar.org/CorpusID:8773578.

[bib.bib23] [23] Valentin Gledel and Nacim Oijid. Avoidance Games Are PSPACE-Complete. In Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté, editors, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), volume 254 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1–34:19, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2023.34.

[bib.bib24] [24] Robert I. Hales and Alfred W. Jewett. Regularity and positional games. Trans. Am. Math. Soc, 106:222–229, 1963.

[bib.bib25] [25] Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó. Positional games, volume 44. Springer, 2014.

[bib.bib26] [26] Dan Hefetz, Michael Krivelevich, and Wei En Tan. Waiter–client and client–waiter planarity, colorability and minor games. Discrete Mathematics, 339(5):1525–1536, 2016. doi:10.1016/j.disc.2015.12.020.

[bib.bib27] [27] Fiachra Knox. Two constructions relating to conjectures of beck on positional games. arXiv preprint arXiv:1212.3345, 2012.

[bib.bib28] [28] Finn Orson Koepke. Solving maker-breaker games on 5-uniform hypergraphs is pspace-complete, 2025. doi:10.48550/arXiv.2502.20271.

[bib.bib29] [29] Martin Kutz. Weak positional games on hypergraphs of rank three. Discrete Mathematics & Theoretical Computer Science, AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb ’05), 2005.

[bib.bib30] [30] Rajko Nenadov. Probabilistic intuition holds for a class of small subgraph games. Proceedings of the American Mathematical Society, 151(04):1495–1501, 2023.

[bib.bib31] [31] Nacim Oijid. Complexity of positional games on graphs. PhD thesis, Université Claude Bernard, Lyon 1, 2024. Thèse de doctorat dirigée par Duchêne, Eric et Parreau, Aline.

[bib.bib32] [32] Md Lutfar Rahman and Thomas Watson. Tractable unordered 3-cnf games. In Latin American Symposium on Theoretical Informatics, pages 360–372. Springer, 2020. doi:10.1007/978-3-030-61792-9_29.

[bib.bib33] [33] Md Lutfar Rahman and Thomas Watson. 6-uniform maker-breaker game is pspace-complete. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS), 2021.

[bib.bib34] [34] Neil Robertson and Paul D Seymour. Graph minors. xiii. the disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65–110, 1995. doi:10.1006/JCTB.1995.1006.

[bib.bib35] [35] Thomas J. Schaefer. On the Complexity of Some Two-Person Perfect-Information Games. Journal of computer and system Sciences, 16:185–225, 1978. doi:10.1016/0022-0000(78)90045-4.

[bib.bib36] [36] Paul D Seymour. Disjoint paths in graphs. Discrete mathematics, 29(3):293–309, 1980. doi:10.1016/0012-365X(80)90158-2.

[bib.bib37] [37] Yossi Shiloach. A polynomial solution to the undirected two paths problem. Journal of the ACM (JACM), 27(3):445–456, 1980. doi:10.1145/322203.322207.

[bib.bib38] [38] Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time (preliminary report). In Proceedings of the fifth annual ACM symposium on Theory of computing, pages 1–9, 1973. doi:10.1145/800125.804029.

On the Complexity of Client-Waiter and Waiter-Client Games

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1 (Erdős-Selfridge criterion).

High-level description of the results

Theorem 2.

Definition 3 (𝖯𝖺𝗂𝗋𝖾𝖽⁢𝖲𝖠𝖳).

Theorem 4.

Theorem 5.

Proposition 6.

Theorem 7.

Organization

2 Preliminaries

Definition 8.

Definition 9.

Lemma 10.

Lemma 11 (Proposition 9 from [12]).

3 Waiter-Client games are FPT on rank k hypergraphs

Proposition 12 (Theorem 1.70 from [31]).

Lemma 13.

Proof.

Theorem 14.

Proof.

Lemma 15.

Proof.

Proof.

4 6-uniform Client-Waiter games are PSPACE-complete

Proposition 16.

Lemma 17.

Theorem 18.

4.1 Reduction to Client-Waiter games

4.1.1 Blocks in Client-Waiter games

Definition 19 (Blocks).

Lemma 20.

Proof.

Corollary 21.

4.1.2 Construction of the hypergraph

Proof of Proposition 16.

4.2 Reduction to 6-uniform hypergraphs

Lemma 22.

Proof.

5 Rank 3 Client-Waiter equivalent to the problem of detecting a tadpole

Definition 23.

Definition 24.

Definition 25.

Lemma 26.

Proof.

6 Open problems

References

Definition 3 ( $\mathsf{Paired\leavevmode\nobreak\ SAT}$ ).