<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*{Degreewidth : un nouveau paramètre pour résoudre des problèmes dans les tournois}
%

% Pour le sommaire
\addcontentsline{toc}{section}{Tom Davot, Lucas Isenmann, Sanjukta Roy et Jocelyn Thiebaut : Degreewidth : un nouveau paramètre pour résoudre des problèmes dans les tournois}
%

% Pour la liste des auteurs
\index{Tom Davot}\index{Lucas Isenmann}\index{Sanjukta Roy}\index{Jocelyn Thiebaut}
%

% Citer un par un les auteurs et leur affiliation
Tom Davot, LIERA, Univeristé d'Angers, {\tt tom.davot@univ-angers.fr}\\
\indent
\underline{Lucas Isenmann}, ICube, Univeristé de Strasbourg, {\tt lucasisenmann@unistra.fr}\\ %souligner l'orateur
\indent
Sanjukta Roy, Czech Technical University in Prague, {\tt sanjukta.roy@fit.cvut.cz}
Jocelyn Thiebaut, Czech Technical University in Prague, {\tt jocelyn.thiebaut@cvut.cz}
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%





\section{Introduction}
 
Nous proposons un nouveau paramètre, appelé degreewidth, pour étudier les problèmes difficiles dans les tournois. 
Ce paramètre mesure à quel point un tournoi est loin d'être acyclique.

Soit $T$ un tournoi. 
Pour un order $\sigma$ sur $V$, un arc $(v_i,v_j)$ est un \emph{arc retour}  si $v_j&lt; v_i$, autrement il est appelé \emph{arc avant}.
Soit $v$ un sommet de $T$, nous notons $d(v)$ le nombre d'arcs retours incidents à $v$ dans $\sigma$. 
Le \emph{degreewidth} de $\sigma$, noté $dw(T, \sigma)$ est donné par $\max\{d(v) \mid v \in V(T)\}$.
Le \emph{degreewidth} de $T$, noté $dw(T)$ est défini comme le minimum de $dw(T, \sigma)$ pour tous les ordres $\sigma$ possibles.
\vspace{0.2cm}

Nous avons démontré les résultats suivants.
\begin{itemize}
    \item Déterminer le degreewidth d'un tournoi est NP-difficile.
    \item Le degreewidth est approchable avec un facteur constant.
\end{itemize}
\vspace{0.2cm}

Nous avons ensuite mis en évidence que le degreewidth pouvait être utilisé en tant que paramètre pour certains problèmes classiques :
\begin{itemize}
    \item {\sc Dominating Set} paramétré par le degreewidth est FPT dans les tournois.
    \item {\sc Feedback Vertex Set} est NP-difficile dans les tournois sparses (c'est-à-dire de degreewidth au plus 1).
\end{itemize}







\begin{thebibliography}{99}

\bibitem{nk1}
DAVOT, Tom, ISENMANN, Lucas, ROY, Sanjukta, et al. Degreewidth: A New Parameter for Solving Problems on Tournaments. In : International Workshop on Graph-Theoretic Concepts in Computer Science. Cham : Springer Nature Switzerland, 2023. p. 246-260.

\end{thebibliography}


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