Introduction

On considère un graphe G = (V, A) orienté. Ce graphe peut posséder des boucles et des arcs symétriques. Des jetons sont disposés dans le graphe, chacun sur un noeud distinct de V. L'objectif est, pour chaque jeton, de se déplacer dans ce graphe sans jamais rencontrer les autres jetons. A chaque étape de déplacement, les jetons vont, de manière synchrone, choisir un arc sortant du noeud où ils se trouvent et suivre cet arc. Le déplacement est valide si, à l'issue de l'étape, chaque jeton est dans un noeud distinct. Nous définissons ainsi le problème de décision No-meet suivant: connaissant un graphe G = (V, A) orienté et S sous-ensemble de V, si on place un jeton dans chaque noeud de S, existe-t-il une suite infinie de déplacements valides pour ces jetons? Dans le cas où la réponse est positive, on dit que S est indépendant. Nous nous sommes intéressés à caractériser les ensembles indépendants de G.

Structure de matroide

Nous avons montré que les sous-ensemble indépendants d'un graphe forment un matroïde, nommé N(G). De plus, le problème No-meet est indépendant, ce qui implique qu'il est possible de trouver une base de N(G) en temps polynomial. Ces bases ont la même taille que la taille maximum de circuits noeuds-disjoints dans G.

Orientation de graphes mixtes

Nous nous sommes également intéressé à des variantes de No-meet dans lesquelles le graphe est mixte. On souhaite orienter le graphe avec plusieurs objectifs possibles:

- rendre S indépendant dans le graphe orienté obtenu. Ce problème est NP-Complet.

- maximiser la taille du plus grand sous-ensemble de S indépendant. Ce problème est NP-Difficile et il n'existe pas de PTAS pour le résoudre. Il est polynomial si |S| = 1.

- minimiser la taille du plus grand sous-ensemble de S indépendant. Ce problème est NP-Difficile. Il est polynomial si |S| = 1.