<p>You may take a look at <a href="http://www.ii.uib.no/~telle/bib/FKT.pdf" rel="nofollow">The Star System Problem revived</a>. Among other things, the authors prove that:</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>In addition, you may find the papers in <a href="http://scholar.google.com/scholar?cites=8154835037185315057&amp;as_sdt=2005&amp;sciodt=2000&amp;hl=en" rel="nofollow">this list</a> useful.</p>

CC BY-SA 2.5
2010-12-19T07:18:12.617Z
Thanks Sadeq, I'm aware of those references and I did not find an answer to my question.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-19T03:06:25.000Z
2010-12-19T03:06:25.000Z
Sadeq Dousti
<p>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.</p>

<blockquote>
  <p>What is the minimum occurrence of each element such that the problem remains $NP$-complete?</p>
</blockquote>

<p><strong>EDIT 12-12-2010</strong>: I added another question:</p>

<blockquote>
  <p>What is the most restricted class of graphs for which the problem remains $NP$-complete?</p>
</blockquote>

<p>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?</p>

<p><a href="http://dx.doi.org/10.1016/0012-365X%2881%2990271-5" rel="nofollow"> F.Lalonde, Le probleme d'etoiles pour graphes est NP-complet, Discrete Math.
33(3), 1981, 271-280.</a></p>

CC BY-SA 2.5
2010-12-15T13:22:21.073Z
The correct link for Lalonde's paper is http://dx.doi.org/10.1016/0012-365X(81)90271-5
Anthony Labarre
CC BY-SA 2.5
2010-09-08T23:45:36.907Z
can you give a reference for the $NP$-completeness of this problem, or (even better) a short argument for it?
Ryan Williams
CC BY-SA 2.5
2010-09-09T00:32:41.407Z
@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
CC BY-SA 2.5
2010-09-09T18:18:54.587Z
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 - http://www.springerlink.com/content/05g8151w58700g66/
Neeldhara
<cc.complexity-theory><np-hardness>
Hardness of constrained star system problem?
Mohammad Al-Turkistany
# Hardness of constrained star system problem?

(Asked by: username_0 on 2010-09-08)

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.](http://dx.doi.org/10.1016/0012-365X%2881%2990271-5)

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_2**: can you give a reference for the $NP$-completeness of this problem, or (even better) a short argument for it?  
> **username_0**: @Williams, it is equivalent to the problem of deciding whether a bipartite graph has an automorphism of order 2 interchanging the two color classes.  
> **username_3**: 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 - http://www.springerlink.com/content/05g8151w58700g66/  
> **username_1**: The correct link for Lalonde's paper is http://dx.doi.org/10.1016/0012-365X(81)90271-5  

---

## 1 answers

### Answer by username_4 on 2010-12-19. Score: 3

You may take a look at [The Star System Problem revived](http://www.ii.uib.no/~telle/bib/FKT.pdf). 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](http://scholar.google.com/scholar?cites=8154835037185315057&as_sdt=2005&sciodt=2000&hl=en) useful.

> **Comments:**
> **username_0**: Thanks Sadeq, I'm aware of those references and I did not find an answer to my question.  

---

