Recherche de cycles.

La recherche de cycles est un problème récurrent en algorithmique des graphes, avec différentes variantes suivant les propriétés recherchées sur ces cycles (par exemple des propriétés de longueur). Les applications sont très nombreuses, allant des problèmes de "postiers" ou "voyageurs de commerce" à l'étude de réseaux de gènes.

L'objectif de ce sujet est de présenter une synthèse sur la complexité de ces recherches. On se concentrera sur la recherche de cycles qui sont des sous-graphes du graphe initial (on pourrait imaginer encore d'autres variantes en les recherchant comme mineurs du graphe initial).
Un singleton ne sera pas considéré comme un cycle.

Pour vous guider, vous pouvez essayer de remplir autant de cases que possibles du tableau ci-dessous (pas forcément tout :-)), en donnant une borne sur la complexité de chacune des variantes proposées. Les lignes décrivent différents critères de recherche de cycles, principalement basés sur la longueur (c'est à dire le nombre d'arêtes ou d'arcs). Les colonnes énumèrent les variantes obtenues en se plaçant dans le cas non orienté ou orienté, et en fonction des différents types de cycles :

• standard (on ne peut pas passer plusieurs fois par une même arête ou arc, mais par contre on peut passer plusieurs fois par un même sommet),
• simple (on ne peut pas passer plusieurs fois par un même sommet),
  
• sans corde (simple et sans arête ou arc qui soit hors du cycle, mais qui joigne deux sommets du cycle ou circuit), dit parfois chordless ou hole en anglais.
  

	Graphes non orientés			Graphes orientés
	cycle quelconque	cycle simple	cycle sans corde	cycle quelconque	cycle simple	cycle sans corde
Existence (sans autre critère)
Longueur maximum
Longueur minimum
Longueur = k, pour un k fixé
Longueur impaire
Longueur paire

Cela fait bien sûr beaucoup de variantes possibles. Certaines correspondent à des problèmes classiques, d'autres moins. Vous pouvez ne donner que le principe général des algorithmes, voire juste une référence, pour certaines variantes dont vous avez la complexité, mais détaillez un algorithme et son analyse pour au moins l'un des problèmes.

Quelques références (pas exhaustif).

• Finding and counting given length cycles, article de N. Alon, R. Yuster et U. Zwick, Algorithmica 17 (1997). Des résultats et des références.
  
• Hole and antihole detection in graphs, article de  D. Nikopoulos et L. Palios, SODA'04 (2004). Des résultats et des références.
• Finding a minimum circuit in a graph, article de A. Itai, STOC'77 (1977). Des résultats et des références.
• Finding even cycles even faster, article de R. Yuster et U. Zwick, SIAM Journal Discrete Math. (1997). Des résultats et des références.
• Detecting even holes, article de M. Chudnovski, K. Kawarabayashi et P. Seymour, Journal Graph Theory 48 (2005). Difficile, mais une réponse.
  
• Digraphs: theory, algorithms and applications, livre de J. Bang-Jensen et G. Gutin, Springer (2002). Voir en particulier le chapitre 10.
  

Retour à la page des sujets.