<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*{Détection de motifs dans les graphes ordonnés}
%

% Pour la liste des auteurs
\index{Ducoffe, G.}%
\index{Feuilloley, L.}%
\index{Habib, M.}%
\index{Pitois, F.}%
%
% Citer un par un les auteurs et leur affiliation
Ducoffe Guillaume, University of Bucharest, Romania, {\tt guillaume.ducoffe@ici.ro}\\
\indent
Feuilloley Laurent, LIRIS, Université Lyon 1, {\tt laurent.feuilloley@univ-lyon1.fr}\\
\indent
Habib Michel, IRIF, Université Paris Cité, {\tt habib@irif.fr}\\
\indent
\underline{Pitois François}, LIRIS, Université Lyon 1, {\tt francois.pitois@univ-lyon1.fr}\\ %souligner l'orateur


% Pour le sommaire
\addcontentsline{toc}{section}{G. Ducoffe, L. Feuilloley, M. Habib et F. Pitois  : Détection de motifs dans les graphes ordonnés}
%

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

Une façon courante de caractériser un graphe est par le biais de sous-graphes ou de mineurs interdits.
Ces caractérisations jouent un rôle central en théorie des graphes, mais ne donnent pas lieu à des algorithmes de reconnaissance efficaces.
À l'inverse, de nombreuses classes de graphes peuvent être reconnues efficacement grâce à une caractérisation d'un autre genre : il faut qu'il existe un ordre des sommets tel qu'un motif n'apparaissent pas, où un motif est un sous-graphe ordonné.
On s'intéresse alors à la question suivante :

\medskip
\textit{Étant donné un motif de taille $k$ fixé, quelle est la meilleure complexité d'un algorithme qui prend en argument un graphe ordonné de taille $n$ et qui donne en sortie si oui ou non ce motif apparait dans ce graphe ?}
\medskip

D'après nos connaissance, cette question n'a jamais été étudiée en détail.
Nous prouvons que quasiment tous les motifs à 3 sommets peuvent être détectés en temps linéaire, tandis que les motifs à 4 sommets nécessitent au moins un temps quadratique.
Nous nous intéressons également à la reconnaissance de plusieurs motifs simultanément : étant donné un graphe ordonné $G$ de taille $n$, quelle est la meilleure complexité pour savoir si au moins un motif d'un ensemble de motifs est présent dans $G$ ?
Dans le cas où il y a au moins 2 motifs et qu'ils sont tous de taille 3, nous montrons qu'il existe un algorithme linéaire pour répondre à cette question. Cela est assez contre-intuitif, puisque dans le cas d'un seul motif à 3 sommets, il n'est pas toujours possible d'atteindre une complexité linéaire.
Enfin, nous définissons un paramètre, la \emph{merge-width}, et nous montrons qu'un motif de \emph{merge-width} $t$ peut être détecté en temps $O(n^{f(t)})$.
Cette borne est applicable directement aux motifs planaires extérieurs, pour lesquels nous prouvons qu'ils ont une \emph{merge-width} de 2.

% A popular way to define or characterize graph classes is via forbidden subgraphs or forbidden minors.
% These characterizations play a key role in graph theory, but they rarely lead to efficient algorithms to recognize these classes.
% In contrast, many essential graph classes can be recognized efficiently thanks to characterizations of the following form: there must exist an ordering of the vertices such that some ordered \emph{pattern} does not appear, where a pattern is basically an ordered subgraph. These pattern characterizations have been studied for decades, but there have been recent efforts to better understand them systematically and algorithmically, following the seminal work of [Hell, Mohar and Rafiey, {\it ESA} 2014].
%
% To our knowledge, the following problem has never been systematically studied, although it is natural in this context.
% The problem of (ordered) pattern detection in ordered graphs consists in deciding whether a small pattern $P$ appears in a large ordered graph $G$ (where an ordered graph is a graph equipped with a total order of its vertices).
% It generalizes two well-studied problems: (unordered) subgraph detection (that deals with the graph structure but not the order) and permutation pattern matching  (that deals with the ordering part, without the graph structure).
%
% We prove a variety of results on this problem. In particular, give a complete characterization of the complexity for patterns on three nodes, describe a generic algorithm beating the naive brute-force, prove conditional lower bounds for the detection of patterns on four nodes, and introduce a new parameter, the merge-width, that captures how easy it is to solve the problem via dynamic programming.

% \begin{theorem}
% Veillez à ce que le résumé n'excède pas {\bf 1 page}.
% \end{theorem}
%
% \begin{corolary}
% Ne réduisez pas la taille de la police.
% \end{corolary}
%
% Si vous souhaitez ajouter une image, faites-en sorte qu'elle soit
% compilable par pdflatex (pas de pstricks ou d'eps). Convertissez-la en
% pdf ou png. L'ajout d'images en Tikz sont également possibles, il vous suffit de décommenter les lignes 10 à 13 du fichier modele.tex pour cela.
%
% \begin{conjecture}
% Dans la mesure du possible, n'ajoutez pas de packages supplémentaires.
% \end{conjecture}
%
%
% \begin{lemma}
% Vous pouvez ajouter des références, comme~\cite{nk1} ci-dessous (avec parcimonie).\footnote{Merci de ne pas utiliser bibtex~!}
% \end{lemma}
%
% Évitez autant que possible de modifier le fichier modele lors de votre soumission. Si vous devez néanmoins faire une modification, merci de nous le signaler lors de la soumission.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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{ducoffe2023pattern}
  Guillaume Ducoffe, Laurent Feuilloley, Michel Habib, and François Pitois,
  \emph{Pattern detection in ordered graphs}, arXiv preprint arXiv\!\!:2302.11619 (2023).

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