CLIQUE natural para redução de k-Color

23

Há claramente uma redução de CLIQUE para k-Color porque ambos são NP-Complete. Na verdade, eu posso construir um compondo uma redução de CLIQUE para 3-SAT com uma redução de 3-SAT para k-Color. O que eu quero saber é se existe uma redução direta razoável entre esses problemas. Digamos, uma redução que eu poderia explicar a um amigo rapidamente, sem precisar descrever uma linguagem intermediária como o SAT.

Como exemplo do que estou procurando, aqui está uma redução direta na direção inversa: Dado G com e algum (número de cores), faça um gráfico G 'com vértices (um por cor por vértice). Os vértices , correspondentes aos vértices e cores respectivamente, são adjacentes se e somente se e ( ou ). Uma nclique em tem apenas um vértice por vértice em , e as cores correspondentes são uma cor adequada dek k n v u v , u c , d v u c d v u G n G G k Gnkknvuv,uc,dvucdvuGnGGkG. Da mesma forma, qualquer cor adequada de tem um clique correspondente em .G G kGG

Edit : Para adicionar uma breve motivação, os 21 problemas originais de Karp são provados NP-Complete por uma árvore de reduções onde CLIQUE e Número Cromático formam as raízes das principais subárvores. Existem algumas reduções naturais entre os problemas na subárvore CLIQUE e na subárvore Número cromático, mas muitos deles são tão difíceis de encontrar quanto o que estou perguntando. Estou tentando detalhar se a estrutura dessa árvore mostra alguma estrutura subjacente nos outros problemas ou se é inteiramente uma conseqüência da qual as reduções foram encontradas primeiro, pois há menos motivação para procurar reduções entre dois problemas quando elas ocorrem. são conhecidos por estar na mesma classe de complexidade. Certamente a ordem teve alguma influência, e partes da árvore podem ser reorganizadas, mas pode ser reorganizada arbitrariamente?

Edit 2 : Continuo a procurar uma redução direta, mas aqui está um esboço do mais próximo que cheguei (deve ser uma redução válida, mas tem CIRCUIT SAT como um intermediário claro; é um pouco subjetivo se isso é melhor do que compondo duas reduções, conforme mencionado no primeiro parágrafo).

Dado , sabemos que pode ser colorido com com vértices com todas as cores True, se tiver uma -clique. os vértices originais de e adicionamos à vértices adicionais: com , . A chave invariante será que pode ser colorido como True se e somente se entre os vértices houver pelo menos vértices coloridos como True. Portanto, cada pode ser True. Então,¯ G n - k + 1 k G k G v 1 , , v n ¯ G C i j 1 i n 0 j k C i j { v 1 , , v i } j C i 0 C i jG,kG¯nk+1kGkG v1,,vnG¯Cij1in0jkCij{v1,,vi}jCi0Cij para obtém a cor que todas as cores não verdadeiras são tratadas como falsas. Existe uma classe em se puder ser colorido como True, portanto, se forçarmos essa coloração, o novo gráfico será colorível se houver uma classe no gráfico original.C ( i - 1 ) jCj>0 kG C n k kC(i1)jC(i1)(j1)vikGCnkk

Os dispositivos AND e OR para impor os relacionamentos são muito parecidos com a redução de CIRCUIT SAT para 3-COLOR, mas aqui incluímos um em nosso gráfico, escolha os vértices T, F e Ground e, em seguida, conecte todos os outros a tudo, exceto aos s; isso garante que os os outros gadgets recebam apenas três cores. v i C i jKnk+1viCij

De qualquer forma, a parte dessa redução parece direta, mas o uso de portas AND / OR é muito menos direto. A questão permanece: existe uma redução mais elegante?G¯

Edit 3 : Houve alguns comentários sobre por que essa redução seria difícil de encontrar. CLIQUE e k-Color são de fato problemas bem diferentes. Mesmo sem uma redução, porém, uma resposta que detalha por que a redução é difícil em uma direção, mas possível na outra seria muito útil e contribuiria muito para o problema.

William Macrae
fonte
4
O tipo de redução direta que você está procurando pode ser difícil de encontrar, pois o Clique e a coloração são opostos, no sentido de que um clique 1 é tão fácil de encontrar quanto um n-coloração. Então, talvez a redução deve ser da forma: tem uma -coloring se e somente se tem um -clique n - k G kGnkGk
Martin Vatshelle
Eu concordo que é difícil; esta é a razão do meu interesse; Vou dar detalhes sobre a motivação na pergunta. O -coloring idéia tem me chegado o mais próximo. Se houver uma -clique em então pode ter todos os vértices no clique monocromático, porque eles são um conjunto independente. O problema é que o número cromático do restante pode variar. Vincular dois vértices a um força a ter a mesma cor, mas não tenho idéia de qual conjunto de vértices forçar. Um gadget que as forças algum fora de vértices para ser monocromática iria fazê-lo. k G ¯ G K n - k - 1 i jnkkGG¯Knk1ij
William Macrae
3
Concordo com Martin aqui que isso pode nem ser possível (sem passar, digamos 3SAT). Clique e coloração têm muito pouco em comum. Quero, portanto, recordar o teorema de Erdős, dados os naturais gek, há um gráfico com perímetro pelo menos ge número cromático pelo menos k (pense nisso por um tempo, se você não estiver familiarizado). Finalmente, sua redução também deve estar ciente de que enquanto o Clique (e o Conjunto Independente) está em parametrizado pelo conjunto de soluções, não há parametrização equivalente para o número cromático de um gráfico. W[1]
precisa
Não entendo o comentário de @ MartinVatshelle. Até onde eu sei, todas as opções 1-clique, 1-cor, n-clique e n-coloração são triviais no mesmo nível. (não acho que você sempre pode atender a 1-clique em YES: o gráfico de entrada pode estar vazio!)
Yixin Cao
Acho que o argumento de Martin é mostrar e , mas é mais difícil encontrar um que um . Portanto, há um pouco de dualidade nos dois conceitos. O argumento de @ PålGD sobre o teorema de Erdős é ótimo (e eu amo esse teorema), pois os gráficos com grande perímetro têm grande número de independência e, portanto, seus inversos terão grandes panelinhas. Globalmente, parece que há uma armadilha aqui no entanto, que é relacionar Panelinhas e corantes nas mesmas ou semelhantes gráficos, mas tal como com a direcção inversa a redução pode construir um gráfico muito diferente do que . χ ( G ) = 3 K 4 K 3 Gχ(G)=4χ(G)=3K4K3G
precisa

Respostas:

14

Dado um grafo e um número k , tal que você quer saber se G contém um k -clique, vamos n ser o número de vértices em G . Construímos outro gráfico H , de modo que H é n- colorido se e somente se G tiver uma k -ique, da seguinte maneira:GkGkGHHnGk

(1) Para cada vértice em G , faça uma n- classe de vértices ( v , i ) em H , onde i varia de 1 a n .vGn(v,i)Hi1n

(2) Adicionar um vértice adicionais para H .xH

{x,y,z}Hy=(v,i)z=(u,j)uvi=juvGn H x y z x y z y x z z x y max(i,j)knH. Dentro dessa camarilha, selecione três vértices , e . Conecte a todos os vértices na clique, exceto e ; conecte a todos os vértices na clique, exceto e ; e conecte a todos os vértices da clique, exceto e .xyzxyzyxzzxy

Os aparelhos adicionados no passo (3) evitar o triplo de vértices , , e de todos a ser dada a mesma cor que o outro em uma coloração válido de . A camarilha em pode ser recuperada a partir de uma coloração de como o conjunto de vértices que estão na mesma classe de cor que e que possuem .y z H G H ( v , i ) x i kxyzHGH(v,i)xik

David Eppstein
fonte
2
Isso é maravilhoso.
precisa
Por alguma razão, minha edição foi rejeitada, mas a última frase deve descrever vértices de G em vez de H (já que se destina a descrever uma clique em G). Algo como "A clique em podem ser recuperados a partir de uma coloração de H, tal como { v : i k χ ( ( v , i ) ) = χ ( x ) } . " Também, se esqueceu de dizer graças para a resposta, tem sido muito útil! G{v:ikχ((v,i))=χ(x)}.
precisa
Claro, você poderia colocar outra cláusula nessa frase sobre retirar o de cada par, mas achei que esse passo era fácil de omitir, e meu sentimento geral é que (quando pode ser curto o suficiente) a prosa tende a ser mais legível que uma fórmula. i
22612 David Eppstein
Concordo que a prosa é mais preferível. Talvez apenas adicionar uma frase como "a primeira coordenada de cada (v, i) ..." seja uma idéia. A razão da minha preocupação com o tecnicismo é que, ao ler as reduções pela primeira vez, pode ser difícil manter retas as definições exatas dos elementos no primeiro idioma e no segundo, e qual é qual. No momento em que algo parece quebrar uma definição, isso pode me dar um loop. Se eu tivesse problemas para entender sentenças anteriores e chegasse à última, determinaria que G e H têm vértices da forma (v, i).
precisa
Devo também dizer que acho que você fez um trabalho muito melhor falando dessa redução do que quase qualquer outra que eu li. Há um problema na literatura de que muitas reduções são declaradas formalmente sem motivação ou intuição, e você evitou isso muito bem.
precisa
-7

?? Sabe-se que a coloração e a descoberta de cliques estão fortemente acopladas há décadas através da teoria dos grafos (possivelmente até nos anos 60?), mesmo que não através do SAT como intermediário (que se tornou típico após a prova de Cook em 1971). Acreditamos que existem algoritmos baseados na seguinte propriedade básica :

Se G contiver um clique do tamanho k, pelo menos k cores serão necessárias para colorir esse clique; em outras palavras, o número cromático é pelo menos o número do clique: χ(G)ω(G).

não tenho certeza das referências exatas, mas [1,2] são bons lugares para começar, um algoritmo exato ou referência é pelo menos provavelmente citado nesses livros.

[1] Cliques, coloração e satisfação, segundo desafio DIMACS

[2] Dimacs vol 26: panelinhas, coloração e satisfação

vzn
fonte
5
Usando a propriedade , pode invocar um algoritmo para k - C S G S R A B I G I T Y em G : Se o algoritmo regressa Y E S , então L não contém nenhum clique de tamanho pelo menos k + 1 . No entanto, a implicação oposta não se aplica: se o algoritmo retornar N O , então G pode ou não ter um clique de tamanho pelo menosχ(G)ω(G)kCOLORABILITYGYESGk+1NOG (como um contra-exemplo, considere uma pirâmide cuja base poligonal tem um número ímpar de vértices: ela não é de 3 cores, mas não possui nenhum clique de tamanho pelo menos 4 ). k+134
Giorgio Camerani
sim combinado; como eu o interpreto, o post original não insistiu na direção da redução, mas enfatizou mais evitar o SAT como intermediário, pedindo uma "explicação breve". Também visivelmente ninguém mencionou o factóide acima até agora .... a questão e comentários também parecem erroneamente indicam de várias maneiras os dois problemas não estão fortemente acoplados ....
vzn
1
Desculpas se a direção foi ambígua. Estou interessado em uma redução correta (SIMSIM) e estou interessado em uma redução de Clique para k-Color. Eu tenho a outra direção e isso é explicado no meu post. Certamente, existem muitas coisas que relacionam cliques em gráficos a cores em gráficos e vice-versa, e de fato já vi muitas delas (e presumo que muitas outras aqui já viram muitas delas), mas estou realmente interessado exclusivamente em redução ou uma explicação convincente do porquê de não existir.
William Macrae
1
@ vzn: Meu comentário não foi feito para criticar sua resposta. Verdade seja dita, inicialmente, eu fiz um raciocínio semelhante ao seu, mas então eu percebi que, se a implicação oposta teria espera, em seguida, em gráficos gerais, que é conhecido por ser NP-completo , teria sido solucionável trivialmente apenas verificando se o gráfico de entrada tinha um clique de 4 nós: qualquer G teria uma cor 3 se e somente se não contiver nenhum clique do tamanho 4 (isso é falso, é claro, como mostra o contra-exemplo da pirâmide). A propósito: não sou eu quem votou mal. 3COLORING4G34
Giorgio Camerani
3
@WilliamMacrae: Era perfeitamente claro que você queria um redução, caso contrário não teria sido uma redução! Além disso, ficou perfeitamente claro que você desejava uma redução de C L I Q U E para C O L O R I N G e não o contrário. CLIQUECOLORING
Giorgio camerani