10
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ can you give a reference for the $NP$-completeness of this problem, or (even better) a short argument for it? $\endgroup$
    – Ryan Williams
    Sep 8, 2010 at 23:45
  • $\begingroup$ @Williams, it is equivalent to the problem of deciding whether a bipartite graph has an automorphism of order 2 interchanging the two color classes. $\endgroup$
    – Mohammad Al-Turkistany
    Sep 9, 2010 at 0:32
  • $\begingroup$ 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 $\endgroup$
    – Neeldhara
    Sep 9, 2010 at 18:18
  • $\begingroup$ The correct link for Lalonde's paper is dx.doi.org/10.1016/0012-365X(81)90271-5 $\endgroup$
    – Anthony Labarre
    Dec 15, 2010 at 13:22

1 Answer 1

Reset to default
3
+25
$\begingroup$

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

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Sadeq, I'm aware of those references and I did not find an answer to my question. $\endgroup$
    – Mohammad Al-Turkistany
    Dec 19, 2010 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.