%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[french]{babel}
\usepackage[T1]{fontenc}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{Un noyau cubique pour l'édition trivialement parfaite}
%

% Pour le sommaire
\addcontentsline{toc}{section}{Un noyau cubique pour l'édition trivialement parfaite}
%

% Pour la liste des auteurs
\index{Dumas, M.}\index{Perez, A.}\index{Todinca, I.}
%

% Citer un par un les auteurs et leur affiliation
\underline{Ma\"el Dumas}, LIFO, Orléans, {\tt mael.dumas@etu.univ-orleans.fr}\\
\indent
Anthony Perez, LIFO, Orléans, {\tt anthony.perez@univ-orleans.fr}\\
\indent
Ioan Todinca, LIFO, Orléans, {\tt ioan.todinca@univ-orleans.fr}\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé
Étant donné un graphe non orienté $G=(V,E)$ et un paramètre entier $k$, le problème de l'édition trivialement parfaite consiste à éditer (ajouter ou supprimer) au plus $k$ arêtes de $G$ pour obtenir un graphe trivialement parfait. Les problèmes de la complétion trivialement parfaite et de la délétion trivialement parfaite sont définis similairement en autorisant uniquement l'ajout ou la suppression d'arêtes respectivement. Les graphes trivialement parfaits sont à la fois cordaux et cographes, ce sont les graphes qui n'admettent ni chemin induit de longueur $4$ ni cycle induit de longueur $4$. Ils ont des applications liées au paramètre de la tree-depth et à l'analyse de réseaux sociaux. Les trois variantes du problème sont connues pour être NP-complètes et admettent des noyaux polynomiaux.

Nous présentons un noyau cubique en nombre de sommets pour les trois variantes du problème, améliorant pour l'édition et la délétion le meilleur noyau connu (de taille $O(k^7)$~\cite{i2}). Ce noyau repose sur la décomposition en cliques universelles des graphes trivialement parfaits et l'identification et la réduction de "bonnes" parties de cette décomposition.
 

\smallskip



\begin{thebibliography}{99}

\bibitem{i2}
P.~G.~Drange and M.~Pilipczuk, \emph{A polynomial kernel for trivially perfect editing}, Algorithmica, {\bf 80(12)}, 3481-3524.

\bibitem{i1}
M.~Dumas, A.~Perez, I.~Todinca, \emph{A Cubic Vertex-Kernel for Trivially Perfect Editing}, MFCS 2021.

\end{thebibliography}


\vfill
\end{document}
