Esta pergunta é semelhante a problemas difíceis de NP em árvores :
Há um grande número de problemas NP-completos que são tratáveis nas cografias . Existem problemas conhecidos que permanecem NP-completos quando restritos a cografias?
Para ser mais preciso, estou interessado em exemplos em que a entrada consiste apenas em uma cografia não direcionada e não ponderada .
Duas observações:
Para cografias ponderadas, esse problema é mencionado aqui - TSP com dois viajantes
As cografias são a "classe base" da largura de clique, como as árvores são a classe base da largura da árvore.
ATUALIZAR
Algumas reflexões adicionais (não tenho muita certeza): se a entrada é realmente apenas uma cografia, a pergunta deve ser do tipo "A cografia tem propriedade X?". Seria suficiente se esse problema existisse para as árvores, desde então a pergunta poderia ser "O cotree da cograph tem propriedade X?".
fonte
Respostas:
Talvez o meu problema aberto favorito seja de interesse: o problema da capa de camarilha nas cografias. No problema de capa de clique de borda, você deseja cobrir as bordas da cografia com um número mínimo de cliques. Não se sabe se esse problema é NP-completo.
fonte
Vários problemas permanecem NP-completos quando restritos a cografias. A coloração da lista, o número acromático e o isomorfismo do subgrafo induzido permanecem NP completos.
[1] Hans L. Bodlaender. O número acromático é NP-completo para cografias e gráficos de intervalo. Inf. Processo. Lett., 31 (3): 135–138, 1989
[2] Klaus Jansen e Petra Scheffler. Coloração generalizada para gráficos em forma de árvore. Discrete Appl. Math., 75 (2): 135-155, 1997
[3] Peter Damaschke. O isomorfismo do subgrafo induzido para as cografias é NP-completo. Notas da Conferência em Ciência da Computação, 1991, Volume 484/1991, 72-78,
fonte
fonte