Hardness of constrained star system problem? A star system is a family $F$ of n subsets of n-elements set $S$. A star system is graphical if there is some graph $G(V,E)$ such that $F$ is the family of vertex neighborhoods in $G$. It is $NP$-complete to decide whether a given star system is graphical.


  What is the minimum occurrence of each element such that the problem remains $NP$-complete?


EDIT 12-12-2010: I added another question:


  What is the most restricted class of graphs for which the problem remains $NP$-complete?


For instance, Is the star system problem $NP$-complete if the target graph is cubic? If not, What is the minimum $k$ such that the problem remains $NP$-complete for $k$-regular target graphs?

 F.Lalonde, Le probleme d'etoiles pour graphes est NP-complet, Discrete Math.
33(3), 1981, 271-280.
You may take a look at The Star System Problem revived. Among other things, the authors prove that:


  if the graph $G$ is required to be $C_k$-free, i.e. not allowed to have an induced cycle of length $k$, then the problem is solvable in polynomial time for each $k \le 4$, and is NP-complete for each $k&gt;5$.


In addition, you may find the papers in this list useful.