¿Cuál es el mejor algoritmo exacto para calcular el núcleo de un gráfico?

24

Un gráfico H es un núcleo si cualquier homomorfismo de H a sí mismo es una biyección. Un subgrafo H de G es un núcleo de G si H es un núcleo y hay un homomorfismo de G a H. http://en.wikipedia.org/wiki/Core_%28graph_theory%29

Dado un gráfico G, ¿cuál es el algoritmo exacto más conocido para encontrar su núcleo?

ds.algorithms graph-theory graph-algorithms Regularidad
fuente
A primera vista, este problema parece muy difícil, pero una reducción del isomorfismo gráfico u otros problemas relacionados no es obvio (para mí). Gran pregunta
Derrick Stolee

Respuestas:

22

Calcular el núcleo de un gráfico es difícil: incluso decidir si un gráfico de 3 colores es un núcleo completo, vea Hell y Nesetril . Hay configuraciones en las que la computación central se puede realizar de manera eficiente; consulte Computación central eficiente en el intercambio de datos por Georg Gottlob y Alan Nash para una configuración de base de datos; aquí algunas restricciones razonables sobre los tipos de restricciones en el esquema de la base de datos permiten que los núcleos se calculen de manera eficiente.

Editar: Aparte del trabajo de Gottlob / Nash mencionado anteriormente, no conozco ningún otro intento de proporcionar algoritmos eficientes para la computación central. Serían bienvenidos los apuntadores a cualquier algoritmo mejor que la fuerza bruta (exacta o no).

András Salamon
fuente
1
Andras, el documento al que enlaza parece mostrar (leyendo el resumen) que verificar si un gráfico es su propio núcleo es NP-completo. ¿El documento también responde a la pregunta que plantea el OP?
Suresh Venkat
8
@Suresh: Creo que señalar la integridad de NP es una de las mejores maneras de responder una pregunta que solicita un algoritmo.
Tsuyoshi Ito
1
Derecha. Me preguntaba si había más en el documento (es decir, ¿puede verificar si el núcleo es pequeño o si el núcleo es trivial, etc., etc.)
Suresh Venkat
9

El problema de determinar si un gráfico dado es un gráfico central se ve fácilmente en co-NP. De hecho, es co-NP completo.

El problema de determinar si un subgrafo H dado es un núcleo de un gráfico G dado está en la clase DP más grande ( https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp ), y de hecho está completo para esta clase ( El problema arquetípico completo para esta clase consiste en pares de fórmulas booleanas, donde la primera es satisfactoria y la segunda es insatificable). La contención en DP es clara: compruebe que G se correlaciona homomórficamente con H (esto se codifica como satisfactoria) y simultáneamente que H no tiene homomorfismo consigo mismo que no está en (esto se codifica como insatisfactoria). La dureza DP no es trivial y se demuestra en el artículo:

Fagin, Ronald, Phokion G. Kolaitis y Lucian Popa. "Intercambio de datos: llegar al núcleo". Transacciones de ACM en sistemas de bases de datos (TODS) 30.1 (2005): 174-210.

Szymon Toruńczyk
fuente
El documento está en dx.doi.org/10.1145/1061318.1061323
András Salamon