La coloration vertex d'un hypergraphe sans restriction d'uniformité NP-difficile? J'ai vu des papiers qui montrent la coloration de vertex pour un hypergraphe de k-unoform est NP-difficile. Cependant, je n'ai pas pu trouver de source expliquant explicitement si une coloration de vertex dans l'hypergraphe général (pas seulement k-uniforme) est NP-difficile.La coloration vertex de l'hypergraphe sans restriction d'uniformité NP-difficile?
Avant de répondre à cette question, il y a beaucoup de choses à expliquer comme la coloration et l'uniformité dans les hypergraphes. Je vais utiliser ici différentes notations. K k-coloring d'un hypergraphe H = (V, E) est une fonction qui attribue des couleurs à partir de {1, 2,. . . , k} aux sommets de H de telle sorte qu'aucun bord ne soit monochromatique (aucun bord n'a tous les sommets de la même couleur - à part les singletons). Le nombre chromatique d'un hypergraphe H est le plus petit entier k pour lequel H admet une coloration k.
Un hypergraphe H = (V, E) est appelé r-uniforme, si tous les arêtes ont une cardinalité (taille) exactement r. La cardinalité d'un hyperede (e) est le nombre de sommets dans (e).
Vous avez déjà trouvé qu'une k-coloration pour l'hypergraphe r-uniforme, r> = 3, est NP-difficile. Si cela est vrai (ce qui est vrai), alors il est NP-difficile pour les hypergraphes généraux, parce que c'est le plus petit problème que les hypergraphes généraux. Pour vous convaincre que cela est vrai, regardons la définition de Berg de l'hypergraphe r-uniforme 1. Ceci est équivalent à la définition ci-dessus.
Voyons désignent r (H) = max | E i |, et s (H) = min | E i |. H est un hypergraphe r-uniforme si r (H) = s (H). Maintenant, si je peux colorer cela en temps polynomail, ce qui signifie que j'ai trouvé le plus petit entier k pour lequel H admet une k-coloration. Alors pour les hypergraphes généraux quand s (H) pourrait être plus petit que r (H), nous serons capables de colorer les sommets en temps polynomial.
Pour trouver la valeur exacte du nombre chromatique d'un hypergraphe est NP-difficile.