Dureté du problème du système stellaire contraint?

Un système d'étoile est une famille de sous - ensembles de n de n éléments-set S . Un système d'étoile est graphique s'il y a un graphe G ( V , E ) de telle sorte que F est la famille des quartiers de sommet dans G . Il est N P- complet de décider si un système d'étoiles donné est graphique.$F$$S$$G(V,E)$$F$$G$$NP$

Quelle est l'occurrence minimale de chaque élément de telle sorte que le problème demeure complet?$NP$

EDIT 12-12-2010 : j'ai ajouté une autre question:

Quelle est la classe de graphes la plus restreinte pour laquelle le problème demeure -complet?$NP$

Par exemple, le problème du système en étoile est-il complet si le graphique cible est cubique? Sinon, quel est le minimum k tel que le problème reste N P -complet pour k- graphes cibles réguliers?$NP$$k$$NP$$k$

F.Lalonde, Le probleme d'etoiles pour graphes est NP-complet, Discrete Math. 33 (3), 1981, 271-280.

Vous pouvez jeter un œil à The Star System Problem revived . Entre autres choses, les auteurs prouvent que:

si le graphe doit être exempt de C k , c'est-à-dire ne pas avoir un cycle induit de longueur k , alors le problème est résoluble en temps polynomial pour chaque k ≤ 4 , et est NP-complet pour chaque k > 5 .$G$$C_k$$k$$k \le 4$$k>5$

De plus, vous pouvez trouver les articles de cette liste utiles.