Hardness of constrained star system problem?
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.