%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}
\usepackage{amsmath}

\newcommand{\tobo}[3]{\ensuremath{>#1, #2, #3>}}

\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{C. Laforest et T. Martinod  : Sur la complexité de la tournée avec transitions obligatoires}
%

% Pour le sommaire
\addcontentsline{toc}{section}{C. Laforest et T. Martinod  : Sur la complexité de la tournée avec transitions obligatoires}
%

% Pour la liste des auteurs
\index{Laforest, C.}\index{Martinod, T.}
%

% Citer un par un les auteurs et leur affiliation
Christian Laforest, LIMOS, Aubière, {\tt christian.laforest@isima.fr}\\
\indent
\underline{Timothée Martinod}, LIMOS, Aubière, {\tt timothee.martinod@uca.fr}\\ %souligner l'orateur
%%%%%% Fin Champs tit %souligner l'orateur
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé
Notre travail s'inscrit dans l'étude du problème de la tournée (voir \cite{VRP}), polynomial dans les graphes complets $K_{n}$. Dans un graphe $G=(V,A)$, une tournée est un parcours $P = u_{0}, \ldots, u_{k-1}$ tel que pour chaque succession $u_{i},u_{j} \in P$, l'arc $(u_{i}u_{j}) \in A$. Le problème de la tournée est défini par un nombre de sources (zéro, une ou plusieurs), un nombre de cibles (une ou plusieurs) et un nombre de tournées à construire (une ou plusieurs). Les \emph{sources} sont les sommets de départ des parcours. Les \emph{cibles} sont des sommets devant appartenir à au moins une des tournées recherchées. Nous étudions ici une variante de ce problème classique. Pour l'exprimer, nous ajoutons à l'instance d'entrée un ensemble $\Pi = \{T_{1}, \ldots, T_{l}\}$. Chaque élément $T_{i}$ de $\Pi$ est appelé une \emph{transition obligatoire}. Nous dirons qu'une tournée $P = u_{0}, \ldots, u_{k-1}$ de $G$ \emph{respecte} la transition obligatoire $T_{i}=~\emph{>a,b,c>}$ si $\forall j = 0, \ldots, k-3$ : $(u_{j} = a, u_{j+1} = b) \implies u_{j+2} = c$. Une tournée $P$ de $G$ \emph{respecte} les transitions obligatoires $\Pi$ si $P$ respecte chaque transition obligatoire qu'elle contient. Nos principaux résultats ici sont les suivants. Nous proposons dans un premier temps un algorithme polynomial pour construire le plus court chemin entre deux sommets d'un graphe avec des transitions obligatoires. Nous montrons que déterminer la longueur minimale d'un parcours respectant les transitions obligatoires à partir d'une source, passant par $c$ cibles données en entrée est non-approximable pour toute constante, même dans $K_{n}$. De même, déterminer la longueur minimale d'un tel parcours passant par tous les sommets du graphe est non-approximable pour toute constante, même dans $K_{n}$. Le résultat précédent est étendu à la recherche d'un parcours hamiltonien (i.e. chaque sommet est parcouru une et une seule fois) suivant les mêmes conditions. Nous montrons que, pour toute constante $x \in \mathbf{N}^+$, déterminer s'il existe un cycle élémentaire, respectant les transitions obligatoires, de taille au moins $\sqrt[x]{n} > 4$ est $\mathcal{NPC}$ même dans $K_{n}$. Nous montrons également qu'aucun algorithme ne peut garantir trouver un cycle élémentaire de taille supérieure à deux (resp. trois) dans un complet $K_{n}$ orienté (resp. non orienté).

\begin{thebibliography}{99}

\bibitem{VRP}
N.~Agatz et al., \emph{The Vehicle Routing Problem: Latest Advances and New Challenges}, Springer US (2008).

\end{thebibliography}


\vfill
\end{document}
