<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%%%%%%%% Champs titre %%%%%%%
% Pour le titre

\subsection*{Complexité du $H$-Game joué sur les arêtes d'un graphe.}
%

% Pour la liste des auteurs
\index{Duchêne, E.}\index{Gledel, V.}\index{Mc Inerney, F}\index{Nisse, N.}\index{Oijid, N.}\index{Parreau, A.}\index{Stojaković, M.}
%
% Citer un par un les auteurs et leur affiliation
Eric Duchêne, LIRIS, Université Lyon 1, {\tt eric.duchêne@univ-lyon1.fr}\\
\indent
Valentin Gledel, Umea University, {\tt valentin.glede@umu.se}\\ %souligner l'orateur 
\indent
Fionn Mc Inerney, TU Wien, {\tt fmcinern@gmail.com}\\ \indent
Nicolas Nisse, INRIA, Université côte d'azur, {\tt nicolas.nisse@inria.fr}\\ \indent
\underline{Nacim Oijid}, LIRIS, Université Lyon 1, {\tt nacim.oijid@univ-lyon1.fr}\\
\indent
Aline Parreau, CNRS, LIRIS, Université Lyon 1, {\tt aline.parreau@univ-lyon1.fr} \\ \indent
Miloš Stojaković, University of Novi Sad, {\tt milosst@gmail.com}\\

% Pour le sommaire
\addcontentsline{toc}{section}{E. Duchêne, V. Gledel, F. Mac Innerney, N. Nisse, N. Oijid, A. Parreau et M. Stojaković  : Complexité du $H$-Game joué sur les arêtes d'un graphe.}
%

%%%%%% Fin Champs titre %%%%%%%%%%%%%%
% Ensuite, le résumé -- 1 PAGE MAXIMUM

\medskip

Nous présentons ici une étude de la complexité du $H$-Game, introduit par Beck. Soit $H$ un graphe fixé. Le $H$-Game est joué sur les arêtes d'un graphe $G$ sur lequel deux joueurs, Maker et Breaker, sélectionnent alternativement une arête libre de $G$. Lorsque toutes les arêtes du graphe ont été sélectionnées, Maker l'emporte si l'ensemble des arêtes qu'elle a prises contient une copie de $H$. Sinon Breaker gagne. Sachant qu'il existe toujours un joueur ayant une stratégie gagnante, le problème étudié est ici : étant donné un graphe $G$, quel joueur a une stratégie gagnante sur $G$ ? La difficulté de ce problème dépendant du graphe $H$ en question, il est naturel de rechercher pour quels graphes $H$, le problème est-il facilement solvable ou non.

\begin{theorem}
    Il existe un arbre $H$ pour lequel il est {\sf PSPACE}-complet de déterminer le gagnant.
\end{theorem}

Le jeu étant déjà difficile pour $H$ un arbre, il devient alors naturel d'ajouter des restrictions, ou paramètres sur les graphes considérés. Dès lors, si $k$ dénote le nombre de coups joués par Maker, nous obtenons les résultats positifs suivants :

\begin{theorem}
    Le $K_{1,\ell}$-game est solvable en temps linéaire sur les arbres. 
    Le $P_4$-game est solvable en temps linéaire sur les graphes. 
\end{theorem}

\begin{theorem}
    Le $H$-Game, paramétré par $k$, est solvable en temps FPT dans les arbres.
    Le $K_{1,\ell}$-Game, paramétré par $k$, est solvable en temps FPT dans les graphes.
\end{theorem}



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

\begin{thebibliography}{99}



%\bibitem{Beck2008}
%J. Beck, \emph{Combinatorial games: Tic-Tac-Toe Theory}, Cambridge: Cambridge University Press, 2008.

\bibitem{duchene2023}
   E. Duchene, V. Gledel, F. Mc Inerney, N. Nisse, N. Oijid, A. Parreau, et M. Stojakovi{\'c}, \emph{Complexity of maker-breaker games on edge sets of graphs}, \href{https://hal.science/hal-03993275}{arXiv preprint arXiv:2302.10972, 2023}


\end{thebibliography}</pre></body></html>