Qual é o melhor algoritmo exato para calcular o núcleo de um gráfico?

24

Um gráfico H é um núcleo se qualquer homomorfismo de H para si é uma bijeção. Um subgrafo H de G é um núcleo de G se H é um núcleo e existe um homomorfismo de G para H. http://en.wikipedia.org/wiki/Core_%28graph_theory%29

Dado um gráfico G, qual é o algoritmo exato mais conhecido para encontrar seu núcleo?

ds.algorithms graph-theory graph-algorithms Regularidade
fonte
À primeira vista, esse problema parece muito difícil, mas uma redução do isomorfismo do gráfico ou de outros problemas relacionados não é óbvia (para mim). Ótima pergunta.
Derrick Stolee

Respostas:

22

É difícil calcular o núcleo de um gráfico: mesmo decidir se um dado gráfico de três cores é um núcleo é co-NP completo, consulte Hell e Nesetril . Existem configurações nas quais a computação central pode ser feita com eficiência; consulte Computação central eficiente no intercâmbio de dados por Georg Gottlob e Alan Nash para obter uma configuração de banco de dados; aqui, algumas restrições razoáveis ​​sobre os tipos de restrições no esquema do banco de dados permitem que os núcleos sejam computados com eficiência.

Edit: Além do trabalho de Gottlob / Nash mencionado acima, não conheço outras tentativas de fornecer algoritmos eficientes para o cálculo do núcleo. Ponteiros para qualquer algoritmo melhor que a força bruta (exata ou não) seriam bem-vindos.

András Salamon
fonte
1
Andras, o artigo ao qual você vincula parece mostrar (lendo o resumo) que verificar se um gráfico é seu próprio núcleo é NP-completo. O artigo também responde à pergunta que o OP faz?
Suresh Venkat
8
@Suresh: Eu acho que apontar a completude do NP é uma das boas maneiras de responder a uma pergunta solicitando um algoritmo.
Tsuyoshi Ito
1
direita. eu só estava me perguntando se havia mais no papel (ou seja, você pode verificar se o núcleo é pequeno, ou se o núcleo é trivial, etc etc)
Suresh Venkat
9

O problema de determinar se um dado gráfico é um gráfico principal é facilmente visto como co-NP. De fato, é co-NP completo.

O problema de determinar se um determinado subgrafo H é o núcleo de um determinado gráfico G está na classe maior DP ( https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp ) e está de fato completo para esta classe ( o problema completo arquetípico dessa classe consiste em pares de fórmulas booleanas, em que a primeira é satisfatória e a segunda insatificável). A contenção no DP é clara: teste que G mapeia homomorficamente para H (isso é codificado como satisfatório) e simultaneamente que H não tem um homomorfismo em si mesmo que não esteja ligado (isso é codificado como insatisfatório). A dureza DP não é trivial e está comprovada no artigo:

Fagin, Ronald, Phokion G. Kolaitis e Lucian Popa. "Troca de dados: chegando ao núcleo." Transações ACM em sistemas de banco de dados (TODS) 30.1 (2005): 174-210.

Szymon Toruńczyk
fonte
O artigo está em dx.doi.org/10.1145/1061318.1061323
András Salamon