gráficos em que a coloração do vértice está em P, mas o conjunto independente é NP completo

19

Existe um exemplo de uma classe de gráficos para a qual o problema de coloração de vértice está em P, mas o conjunto independente de problema é NP completo?

Ankur
fonte
11
há um sentido no qual a computação de um dos dois esteja aparentemente firmemente acoplado, ver a sanduíche Lovasz THM etc
vzn

Respostas:

21

Uma afirmação talvez mais geral (com uma prova fácil) é que o seguinte problema já está completo no NP:

Entrada: Um gráfico G, uma coloração 3 de G, um número inteiro k.

Pergunta: G tem um conjunto independente de tamanho k?

Isso pode ser comprovado por uma redução do Independent Set. Observe que, se pegarmos um gráfico G, escolher uma aresta e subdividi-la duas vezes (ou seja, substituir a aresta {u, v} por um caminho u, x, y, v onde xey tenham grau dois), então o número de independência de G aumenta exatamente um. (Você pode adicionar exatamente um de x ou y a qualquer conjunto que fosse independente em G e o inverso também não é difícil.) Portanto, a pergunta se o gráfico G com m arestas tem um conjunto independente de tamanho k é equivalente à pergunta se G ', que é o resultado da subdivisão de todas as arestas em G duas vezes, tem um conjunto independente de tamanho k + m. Mas observe que é fácil obter uma coloração 3 de G ', particionando G' em três conjuntos independentes da seguinte maneira: um contém os vértices que também estavam em G e as outras duas classes contêm exatamente um dos dois " subdivisor " vértices para cada aresta. Portanto, este procedimento constrói um gráfico G 'com uma coloração 3, de tal forma que calcular seu número de independência forneça o número de independência do gráfico original G.

Bart Jansen
fonte
4
Essa redução também prova imediatamente a dureza do conjunto independente em gráficos planares sem triângulo, pela minha resposta, sem referência a trabalhos de difícil obtenção.
David Eppstein
22

Supostamente, a referência "problemas de NP-completos em um gráfico planar cúbico de 3 conexões e suas aplicações" de Uehara (um artigo que eu realmente não vi) prova que o conjunto independente é NP-completo mesmo para gráficos planares sem triângulo. Mas por teorema de Grötzsch, eles são sempre tricolores, e testar em números menores de cores que 3 é fácil em qualquer gráfico, para que possam ser otimamente coloridos em P.

Os gráficos de círculo têm a propriedade oposta: para eles, a coloração é NP completa, mas o problema do conjunto independente é fácil.

David Eppstein
fonte
2
Você tem certeza dos gráficos de círculo? A página da wiki diz que "o número cromático de um gráfico circular pode ser arbitrariamente grande, e determinar o número cromático de um gráfico circular é NP-completo".
Ankur #
Opa, entendi ao contrário. Fixará.
David Eppstein
Obrigado. Seria ótimo obter outros exemplos. O artigo de Uehara parece um pouco isolado; não há muitos outros documentos citando-o. Não tenho certeza se foi revisado e publicado por pares.
Ankur
11

Esta não é uma resposta nova, mas sim um esclarecimento, a primeira e fácil referência de dureza de INDEPENDENT SET em gráficos planares cúbicos sem triângulo: A nota de Owen Murphy, Computando conjuntos independentes em gráficos com grande perímetro , Matemática Aplicada Discreta 35 (1992) 167-170 prova que

ncnkc>0k,0k<1

cc>0

A redução indicada por @BartJansen é um caso especial na prova de Murphy de seu teorema.

Para a propriedade oposta, os gráficos de linha parecem ser mais naturais que os gráficos de círculo, conforme endereçado por @DavidEppstein. Para gráficos de linhas, COLORING é NP-completo, mas INDEPENDENT SET é fácil.

user13136
fonte
6
Outro exemplo interessante para a propriedade oposta é a classe de gráficos bem cobertos (veja aqui e aqui ). Para eles, Colorir é difícil, mas o Conjunto Independente é trivialmente fácil.
vb le