# 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.

• can you give a reference for the $NP$-completeness of this problem, or (even better) a short argument for it? – Ryan Williams Sep 8 '10 at 23:45
• @Williams, it is equivalent to the problem of deciding whether a bipartite graph has an automorphism of order 2 interchanging the two color classes. – Mohammad Al-Turkistany Sep 9 '10 at 0:32
• As a side note: if you require the witness graph $G$ to exclude a path/cycle on at most four vertices, then the problem is polynomial time - springerlink.com/content/05g8151w58700g66 – Neeldhara Sep 9 '10 at 18:18
• The correct link for Lalonde's paper is dx.doi.org/10.1016/0012-365X(81)90271-5 – Anthony Labarre Dec 15 '10 at 13:22

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>5$.