Dans un graphique, un ensemble indépendant est un sous-ensemble de sommets qui ne contient pas d'arête comme sous-graphique induit. Le problème de trouver les plus grands ensembles indépendants dans un graphique est une question algorithmique fondamentale, et difficile à résoudre. Considérons la question plus générale de trouver (la taille de) un plus grand ensemble sans H dans un graphique, où H sans signifie qu'il n'induit pas un sous-graphique qui contient une copie du graphique fixe H en tant que sous-graphique induit.
Pour le graphe fixe H, étant donné le graphe d'entrée G, est-il difficile de déterminer la taille d'un plus grand ensemble sans H dans G?
Existe-t-il un moyen judicieux de construire un "tableau" de graphiques H (ou classes de H), de manière à remplir les entrées avec des réponses correctes oui ou "non" à la question ci-dessus? (Imaginons que "non" = P, et même qu'une entrée "non" signifie qu'il existe un algorithme de polytime pour générer un plus grand ensemble sans H.)
A défaut, existe-t-il des classes non triviales de H pour lesquelles la réponse est oui? ... non?
Je cherchais autour de moi, examinant deux questions sur les nombres chromatiques généralisés / sans H --- ici et ici --- quand il m'est venu à l'esprit que le problème (du moins ostensiblement plus simple) "double" d'un analogue sans H du nombre d'indépendance pourrait également être ouvert. Je connais des articles classiques sur un problème connexe pour les graphes aléatoires, cf. par exemple Erdos, Suen et Winkler (1995) ou Bollobas et Thomason (2000), qui sont dans une ligne de recherche encore très active. Donc, il y a peut-être déjà un travail que je n'ai pas encore vu aborder cette question plus fondamentale et qu'une recherche Internet approximative n'a pas découverte (d'où la balise de demande de référence).
Réponses:
[1] John M. Lewis, Mihalis Yannakakis: Le problème de suppression de nœuds pour les propriétés héréditaires est NP-complet. J. Comput. Syst. Sci. 20 (2): 219-230 (1980)
la source