¿Dureza del problema del sistema estelar restringido?

Un sistema de la estrella es una familia de n subconjuntos de n-elementos establecidos . Un sistema de estrellas es gráfico si hay algún gráfico tal que es la familia de los barrios vértice en . Es completo para decidir si un sistema estelar dado es gráfico. $F$ $S$ $G(V,E)$ $F$ $G$ $NP$

¿Cuál es la ocurrencia mínima de cada elemento para que el problema siga siendo -completo? $NP$

EDITAR 12-12-2010 : agregué otra pregunta:

¿Cuál es la clase de gráficos más restringida para la cual el problema sigue siendo -completo? $NP$

Por ejemplo, ¿el problema del sistema estelar es -completo si el gráfico objetivo es cúbico? Si no es así, ¿cuál es el mínimo para que el problema siga siendo -completo para gráficos de objetivos regulares? $NP$ $k$ $NP$ $k$

F.Lalonde, Le probleme d'etoiles pour graphes est NP-complet, Discrete Math. 33 (3), 1981, 271-280.

cc.complexity-theory np-hardness Mohammad Al-Turkistany
fuente

N P

$NP$

@Williams, es equivalente al problema de decidir si un gráfico bipartito tiene un automorfismo de orden 2 que intercambia las dos clases de color.

Mohammad Al-Turkistany

G

$G$

El enlace correcto para el artículo de Lalonde es dx.doi.org/10.1016/0012-365X(81)90271-5

Anthony Labarre

Respuestas:

Puede echar un vistazo a El problema del sistema estelar revivido . Entre otras cosas, los autores prueban que:

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

Además, puede encontrar útiles los documentos de esta lista .

MS Dousti
fuente

Gracias Sadeq, conozco esas referencias y no encontré una respuesta a mi pregunta.

Mohammad Al-Turkistany