Ensembles indépendants dans les graphes : structure, décompositions et applications

Résumé de la thèse

L’un des problèmes les plus fondamentaux en théorie algorithmique des graphes est le calcul d’un ensemble indépendant maximum. Ce problème est étroitement lié à la modélisation des réseaux Wi-Fi, qui peuvent être naturellement représentés comme des graphes de conflits, où les sommets correspondent aux appareils et les arêtes représentent les interférences. En raison des contraintes des protocoles, les appareils actifs simultanément doivent former un ensemble indépendant. Par conséquent, les performances (débits) des appareils dépendent de la distribution des ensembles indépendants dans le graphe. Cette observation soulève des questions algorithmiques et structurelles naturelles : quelles classes de graphes garantissent de bonnes performances, comment attribuer efficacement les canaux, et comment estimer ces mesures de performance. Nous étudions d’abord les graphes dans lesquels chaque sommet appartient à au moins un ensemble indépendant maximum, appelés graphes 1-extendable. Ces graphes garantissent un niveau minimal de performance pour tous les dispositifs. Nous examinons la complexité de la reconnaissance de tels graphes et montrons que ce problème est Theta_2^p-complet, établissant ainsi sa complexité exacte. Motivés par le problème d'attribution de canaux, nous introduisons les k-partitions 1-extendable, où l’ensemble des sommets est partitionné en k sous-graphes, chacun vérifiant cette propriété. Bien que difficile en général, nous proposons des algorithmes en temps polynomial pour certaines classes de graphes restreintes, comme celles de graphes de largeur modulaire bornée. Nous considérons ensuite une notion plus robuste fondée sur la sous-coloration, où chaque partie induit une union disjointe de cliques, garantissant une stabilité vis-à-vis des suppressions de sommets. Nous étudions ce problème dans les graphes d’intersection géométriques, qui modélisent naturellement les réseaux sans fil. Pour des classes importantes telles que les graphes de disques unitaire, nous établissons des résultats de NP-complétude ainsi que des bornes sur le nombre de couleurs. Nous concevons également et évaluons expérimentalement une heuristique simple, montrant que la sous-coloration améliore significativement l’équité dans des scénarios pratiques d’attribution de canaux. Pour estimer les performances des dispositifs, nous analysons le modèle hard-core, une distribution de probabilité sur les ensembles indépendants, ainsi que la dynamique de Glauber associée. Nous montrons que, bien que le temps de mélange soit exponentiel en général, il devient sous-exponentiel pour plusieurs classes de graphes géométriques (par exemple 2^{O(sqrt{n})} pour les graphes de disques unitaire), ce qui conduit à des algorithmes randomisés pratiques. Nous obtenons en outre des bornes quasi-polynomiales sous certaines contraintes structurelles, telles qu’un nombre d’indépendance arborescent borné, et prouvons qu’elles sont optimales. Enfin, nous étudions l’existence d’algorithmes sous-exponentiels pour la sous-coloration dans les graphes géométriques. À l’aide d’une nouvelle décomposition fondée sur des graphes ayant de petits ensembles indépendants, nous concevons un algorithme s’exécutant en temps 2^{O(n^{1 - 1/(d+1)})} pour calculer des 2-sous-colorations et établissons des bornes inférieures correspondantes. Ce résultat ne s’inscrit pas dans les cadres classiques pour les graphes d’intersection géométriques. En nous appuyant sur cette approche, nous introduisons une autre décomposition, reposant également sur des graphes à petits ensembles indépendants comme briques de base, et obtenons un algorithme robuste sous-exponentiel pour le problème du chemin hamiltonien.

One of the most fundamental problems in algorithmic graph theory is the computation of a maximum independent set. This problem is closely connected to the modeling of Wi-Fi networks, which can be naturally represented as conflict graphs, where vertices correspond to devices and edges represent interference. Due to protocol constraints, simultaneously active devices must form an independent set. Consequently, the performance (throughput) of a device depends on the distribution of independent sets in the graph. This observation raises natural algorithmic and structural questions: which graph classes guarantee good performance, how to assign channels efficiently, and how to estimate these performance measures. We first study graphs in which every vertex belongs to at least one maximum independent set, called 1-extendable graphs. These graphs ensure a minimum level of performance for all devices. We investigate the computational complexity of recognizing such graphs and show that this problem is Theta_2^p-complete, settling its precise complexity. Motivated by channel assignment, we introduce 1-extendable k-partitions, where the vertex set is partitioned into k subgraphs, each ensuring this property. While hard in general, we provide polynomial-time algorithms for restricted graph classes, such as those of bounded modular-width. We then consider a more robust notion based on subcoloring, where each part induces a disjoint union of cliques, ensuring stability under vertex deletions. We study this problem in geometric intersection graphs, which naturally model wireless networks. For important classes such as unit disk graphs, we establish NP-completeness results and bounds on the number of colors. We also design and experimentally evaluate a simple heuristic, showing that subcoloring significantly improves fairness in practical channel assignment scenarios. To estimate device performance, we analyze the hard-core model, a probability distribution over independent sets, and its associated Glauber dynamics. We show that, although the mixing time is exponential in general, it becomes subexponential for several geometric graph classes (e.g., 2^{O(sqrt{n})} for unit disk graphs), yielding practical randomized algorithms. We further obtain quasi-polynomial bounds under structural restrictions, such as bounded tree-independence number, and prove their near-optimality. Finally, we investigate the existence of subexponential algorithms for subcoloring in geometric graphs. Using a novel decomposition based on graphs with small independent sets, we design an algorithm running in time 2^{O(n^{1 - 1/(d+1)})} for computing 2-subcolorings and prove matching lower bounds. This result does not fit into classical frameworks for geometric intersection graphs. Building on this approach, we introduce another decomposition, again using graphs with small independent sets as building blocks, and obtain a subexponential robust algorithm for the Hamiltonian Path problem.