Mots-clef : Complexité, Graphe, Domination, Obligation.

Domaine d'application : Réseaux/capteurs.

Un sous-ensemble D ⊆ V est un ensemble dominant indépendant (ou stable) d’un graphe G = (V, E) si D est un ensemble indépendant (aucune arête entre les sommets de D) et dominant tous les sommets de G (chaque sommet de V − D a un voisin dans D). Nous étudions une généralisation de cette notion. Une instance de notre problème est un graphe G = (V, E) et Π = (V1, . . . , Vk) une partition de V. Chaque sous-ensemble Vi de Π est appelé une obligation. Un ensemble Dominant Indépendant avec Obligations (IDO) D dans une instance (G, Π) est un ensemble dominant indépendant de G avec la contrainte supplémentaire que si un sommet u d’une obligation Vi est dans D, alors tous les autres sommets de Vi doivent aussi appartenir à D : pour chaque i = 1, . . . , k, soit Vi ∩ D = ∅ soit Vi ⊆ D (on dit que D respecte les obligations). S’il existe une constante λ telle que pour chaque i = 1, . . . , k, |Vi| = λ alors les obligations sont dites λ-équilibrées. Si chaque obligation de Π est un singleton, un IDO est simplement un ensemble dominant indépendant de G qui peut être construit avec un algorithme glouton. Au contraire, déterminer l'existence d'un IDO dans un chemin est un problème NP-complet, même si les obligations sont stables et (λ ≥ 2)-équilibrées. 

Mots-clef : Complexité, Graphe, Tournées de véhicules, Obligation.

Domaine d'application : Logistique/tournées.

Dans un graphe G = (V, A), une tournée est un parcours P = u0, . . . , uk−1 tel que pour chaque succession ui, uj ∈ P , l’arc (uiuj ) ∈ 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 sources sont les sommets de départ des parcours. Les 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 Π = {T1, . . . , Tl}. Chaque élément Ti de Π est appelé une transition obligatoire. Une tournée P = u0, . . . , uk−1 de G respecte la transition obligatoire (Ti = >a,b,c>) si ∀j = 0, . . . , k − 3 : (uj = a, uj+1 = b) ⇒ uj+2 = c. Une tournée P de G respecte les transitions obligatoires Π si P respecte chaque transition obligatoire associée au graphe. Construire un plus court chemin entre deux sommets d'un graphe avec des transitions obligatoires demeure polynomial. Cependant, trouver le plus court chemin élémentaire entre deux sommets d'un digraphe est non-approximable pour tout ratio, même si chaque sommet possède |V| - 2 arcs sortants. 

Mots-clef : Complexité, Graphe, Approximation, Sous-graphe équilibré.

Domaine d'application : Réseaux.

Un sous-graphe G′ = (M, E(M)) forme un sous-graphe induit d’un graphe G = (V, E) si les sommets M sont incluent dans les sommets V et si chaque arête de E(M) appartient à E. Nous étudions cette notion à travers des motifs connexes quelconques et des motifs connexes formés par deux couleurs dont la répartition est équilibrée. Une instance de notre problème de la recherche d’un sous-graphe est un graphe coloré (sans nécessiter que la coloration soit propre) et un motif. Une solution est un sous-graphe connexe dont la coloration des sommets correspond au motif choisi. Déterminer la présence d'un motif est un problème NP-complet, même dans un graphe de blocs. De même, trouver le plus grand sous-graphe connexe équilibré (pour deux couleurs) est un problème non-approximable pour toute constante, même dans les graphes cordaux, planaires et de diamètre maximum trois.