<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%Compiler avec pdflatex, le résultat ne doit pas dépasser une page
%Merci de respecter scrupuleusement ce modèle.
\documentclass[a4paper,titlepage,12pt,normalheadings,makeidx]{article}
\usepackage{graphicx} 
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{Complexité des jeux Waiter-Client}
%

% Pour le sommaire
\addcontentsline{toc}{section}{V. Gledel, N. Oijid, S. Tavenas et S. Thomassé: Complexité des jeux Waiter-Client}
%

% Pour la liste des auteurs
\index{Gledel, V.}\index{Oijid, N.}\index{Tavenas, S.}\index{Thomassé, S.}
%

% Citer un par un les auteurs et leur affiliation
Valentin Gledel, LAMA, Univ. Savoie Mont Blanc, {\tt valentin.gledel@univ-smb.fr}\\
\indent
\underline{Nacim Oijid}, LaBRI, Univ. de Bordeaux, {\tt nacim.oijid@u-bordeaux.fr}\\%souligner l'orateur
\indent
Sébastien Tavenas,  LAMA,  Univ. Savoie Mont Blanc, {\tt sebastien.tavenas@univ-smb.fr}\\
\indent
Stéphan Thomasé, LIP, ENS de Lyon, {\tt stephan.thomasse@ens-lyon.fr}\\

%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé

%Les jeux positionnels ont été introduits par Hales et Jewett en 1963, et leur étude s'est intensifié après les premiers résultats d'Erd\H os et Selfridge montrant leur connexion avec la théorie de Ramsey et la coloration d'hypergraphe en 1973. Différentes conventions de jeux existent, et la plus populaire, Maker-Breaker considère deux joueurs, Maker et Breaker qui vont à tour de rôle choisir un sommet d'un hypergraphe jusqu'à ce que tous les sommets soient choisis Maker l'emporte alors si elle a rempli une hyperarête, sinon c'est Breaker qui l'emporte. Cette convention a été prouvée PSPACE-complète par Schaefer en 1978. L'étude de la complexité des jeux positionnels s'est alors ralenti jusqu'à un nouvel intérêt récent pour ce domaine. En 2017, Bonnet, Jamain, and Saffidine ont prouvé que les jeux Maker-Breaker étaient W[1]-dur paramétré par le nombre de coup accordé à Maker pour gagner. En 2021, Rahman et Watson ont amélioré le résultat de PSPACE-difficulté de Schaefer en montrant qu'on pouvait se restreindre aux hypergraphes de rang $6$, et en 2024, Galliot, Gravier et Sivignon ont prouvé que le gagnant pouvait être déterminé en temps polynomial si l'hypergraphe était de rang $3$.

%On s'intéresse ici à l'étude de la convention de jeux Waiter-Client, introduite par Beck en 2002 sous le nom "Picker-Choose" dans le but de mieux comprendre les jeux Maker-Breaker. Dans cette convention, Waiter choisis deux sommets libres de l'hypergraphe et les présent à Client qui choisira un des deux sommets qu'il prendra et laissant le second sommet à Waiter. Waiter l'emporte si elle parvient à avoir tous les sommets d'une hyperarête, sinon Client l'emporte. Cette convention a été prouvée NP-dur par Csernenszky, Martin et Pluhar en 2011, mais ni la complétude ni résultats positifs n'étaient connus jusqu'à présent. Nous proposons ici un algorithme FPT, paramétré par le rang de l'hypergraphe pour déterminer le gagnant de ces jeux, prouvant au passage que calculer le gagnant des polynomial sur les hypergraphes de rang borné, résultat surprenant au vue de la complexité des autres conventions de jeux positionnels. 


Les jeux positionnels ont été introduits par Hales et Jewett en 1963, et leur étude s'est intensifiée après les premiers résultats d'Erdős et Selfridge, qui ont montré en 1973 leur connexion avec la théorie de Ramsey et la coloration d'hypergraphes. Différentes conventions de jeux existent, et la plus populaire, le jeu Maker-Breaker, fait intervenir deux joueurs, Maker et Breaker, qui choisissent à tour de rôle un sommet d'un hypergraphe jusqu'à ce que tous les sommets soient choisis. Maker l'emporte si elle parvient à compléter une hyperarête, sinon c'est Breaker qui gagne. Cette convention a été prouvée PSPACE-complète par Schaefer en 1978. L'étude de la complexité des jeux positionnels s'est ensuite ralentie jusqu'à un regain d'intérêt récent pour ce domaine. En 2017, Bonnet, Jamain et Saffidine ont prouvé que les jeux Maker-Breaker étaient W[1]-durs, paramétrés par le nombre de coups accordés à Maker pour gagner. En 2021, Rahman et Watson ont amélioré le résultat connu de PSPACE-difficulté en montrant qu'il était possible de se restreindre aux hypergraphes de rang 6, et en 2024, Galliot, Gravier et Sivignon ont prouvé que le gagnant pouvait être déterminé en temps polynomial si l'hypergraphe était de rang 3.

Nous nous intéressons ici à l'étude de la convention Waiter-Client, introduite par Beck en 2002 sous le nom de "Picker-Chooser", dans le but de mieux comprendre les jeux Maker-Breaker. Dans cette convention, Waiter choisit deux sommets libres de l'hypergraphe et les présente à Client, qui choisit l'un des deux sommets à prendre, laissant le second à Waiter. Waiter l'emporte si elle parvient à obtenir tous les sommets d'une hyperarête, sinon Client gagne. Cette convention a été prouvée NP-difficile par Csernenszky, Martin et Pluhar en 2011, mais aucun résultat positif ni aucun résultat de complétude n'étaient connus jusqu'à présent. Nous proposons ici un algorithme FPT, paramétré par le rang de l'hypergraphe, pour déterminer le gagnant de ces jeux, prouvant ainsi que le calcul du gagnant est polynomial sur les hypergraphes de rang borné.  

\smallskip

\smallskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Eventuellement, une figure, pdf ou png (PAS eps)
%\begin{figure}[htb]
%\begin{center}
%\includegraphics[height=3cm]{gtree}
%\caption{Un graphe.
%\label{fig:graphe}}
%\end{center}
%\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






\vfill
\end{document}
</pre></body></html>