Dureza do problema do sistema estelar restrito?

Um sistema da estrela é uma família de n subconjuntos de N-elementos fixados S . Um sistema da estrela é gráfica, se houver algum gráfico G ( V , E ) de modo a que F é a família dos bairros de vértice em L . É N P -Complete para decidir se um determinado sistema estelar é gráfica.$F$$S$$G(V,E)$$F$$G$$NP$

Qual é a ocorrência mínima de cada elemento de tal forma que o problema permanece -completo?$NP$

EDIT 12-12-2010 : adicionei outra pergunta:

O que é a classe mais restrita de gráficos para as quais o problema permanece -completo?$NP$

Por exemplo, o problema do sistema em estrela está completo se o gráfico de destino for cúbico? Se não, o que é o mínimo k tal que o problema permanece N P completos para k gráficos alvo -Regular?$NP$$k$$NP$$k$

F.Lalonde, O problema dos arquivos de gráficos é NP-complete, Discrete Math. 33 (3), 1981, 271-280.

Você pode dar uma olhada no The Star System Problem revivido . Entre outras coisas, os autores provam que:

$G$$C_k$$k$$k \le 4$$k>5$

Além disso, você pode achar úteis os papéis nesta lista .