Famílias de gráficos que possuem algoritmos de tempo polinomial para calcular o número cromático

23

Postagem atualizada em 31 de agosto : Adicionei um resumo das respostas atuais abaixo da pergunta original. Obrigado por todas as respostas interessantes! Obviamente, todos podem continuar postando novas descobertas.


Para quais famílias de gráficos existe um algoritmo polinomial de tempo para calcular o número cromático ?χ(G)

O problema é solucionável no tempo polinomial quando (gráficos bipartidos). Em geral, quando χ ( G ) 3 , o cálculo do número cromático é NP-difícil, mas existem muitas famílias de gráficos em que esse não é o caso. Por exemplo, ciclos de coloração e gráficos perfeitos podem ser feitos em tempo polinomial.χ(G)=2χ(G)3

Além disso, para muitas classes de gráficos, podemos simplesmente avaliar o polinômio cromático correspondente; alguns exemplos no Mathworld .

Suponho que a maioria dos itens acima é de conhecimento comum. Eu ficaria feliz em saber se existem outras famílias de gráficos (não triviais) para as quais a coloração mínima do gráfico é solucionável em tempo polinomial.

Em particular, estou interessado em algoritmos exatos e determinísticos, mas sinta-se à vontade para apontar qualquer algoritmo aleatório interessante ou algoritmo de aproximação.


Atualização (31 de agosto):

Obrigado a todos por enviar respostas interessantes. Aqui está um breve resumo das respostas e referências.

Gráficos perfeitos e quase perfeitos

  • Algoritmos geométricos e otimização combinatória (1988), Capítulo 9 (Conjuntos estáveis ​​em gráficos). Martin Grotschel, Laszlo Lovasz, Alexander Schrijver.

    O capítulo 9 do livro mostra como resolver o problema de coloração através do problema de cobertura de clique mínimo ponderado. Como eles se baseiam no método elipsóide, esses algoritmos podem não ser muito úteis na prática. Além disso, o capítulo possui uma boa lista de referências para diferentes classes de gráficos perfeitos.

  • Otimização Combinatória (2003), Volume B, Seção VI Alexander Schrijver.

    Este livro tem três capítulos dedicados a gráficos perfeitos e sua capacidade de coloração polinomial. Dei apenas uma olhada rápida, mas a abordagem básica parece a mesma do livro anterior.

  • Uma caracterização de gráficos b-perfect (2010). Chinh T. Hoàng, Frédéric Maffray, Meriem Mechebbek

Gráficos com largura de árvore delimitada ou largura de clique

  • Conjunto e cores dominantes das arestas em gráficos com largura de clique fixa (2001). Daniel Kobler, Udi Rotics

    Os algoritmos aqui requerem uma expressão k (uma fórmula algébrica para construir um gráfico com uma largura de clique limitada) como parâmetro. Para alguns gráficos, essa expressão pode ser calculada em tempo linear.

  • Yaroslav apontou em métodos para contar cores em gráficos de largura de árvore delimitados. Veja a resposta dele abaixo.

k

Gráficos que não contêm subgráficos específicos

Colorir quadtrees

Joel Rybicki
fonte
1
Gráficos de comparação. Essa é provavelmente uma das famílias triviais, mas ainda acho que elas devem ser mencionadas, e é por isso que uso um comentário em vez de uma resposta.
Radu GRIGore
Você quis dizer gráficos de comparabilidade ou gráficos de comparação são uma classe diferente?
Joel Rybicki
Eu quis dizer gráficos de comparabilidade, que são perfeitos.
Radu GRIGore
Observe que os gráficos b-perfect estão "próximos" de serem perfeitos, mas não o são, pois podem conter 5 ciclos.
András Salamon
Seu link para o artigo de Cai está incorreto.
Jeremy Kun

Respostas:

14

Como você observa, todos os gráficos perfeitos podem ser coloridos em tempo polinomial, mas acho que a prova envolve algoritmos elipsóides para programação linear (veja o livro de Grötschel, Lovász e Schrijver) em vez de qualquer coisa direta e combinatória. Existem muitas classes diferentes de gráficos que são subclasses de gráficos perfeitos e possuem algoritmos de coloração mais fáceis; gráficos de acordes, por exemplo, podem ser coloridos com avidez usando uma ordem de eliminação perfeita.

Todos os gráficos conectados localmente (gráficos nos quais todo vértice tem uma vizinhança conectada) podem ter três cores em tempo polinomial, quando existe uma coloração: basta estender o triângulo da coloração por triângulo.

Gráficos de grau máximo três podem ser coloridos em tempo polinomial: é fácil testar se são bipartidos; caso contrário, eles exigem apenas três cores ou têm K4 como componente conectado e quatro cores (teorema de Brooks).

Os gráficos planares sem triângulo podem ser coloridos em tempo polinomial, pelo mesmo motivo: eles são no máximo 3-cromáticos (teorema de Grötzsch).

David Eppstein
fonte
8

Os gráficos b-perfect permitem 5 ciclos induzidos (diferentemente dos gráficos perfeitos) e mostraram um algoritmo de tempo polinomial para colorir por Hoàng, Maffray e Mechebbek, uma caracterização de gráficos b-perfect , arXiv: 1004.5306 , 2010.

(É uma pena que o maravilhoso compêndio de classes de gráficos da ISGCI cubra apenas a largura de cliques, conjunto independente e dominação. Não inclui informações sobre cores.)

András Salamon
fonte
Em relação ao ISGCI: Se conjuntos independentes são fáceis, pode ser uma indicação de que a cor também pode ser fácil. Portanto, a navegação no ISGCI pode fornecer novas idéias para pesquisas adicionais.
Jukka Suomela
Além disso, muitos dos artigos citados no ISGCI consideram a coloração e também o CLIQUE / CONJUNTO INDEPENDENTE. Mas existem mais de 1000 referências para percorrer ...
András Salamon
Obrigado. ISGCI parece promissor, então talvez eu faça alguma navegação por lá.
Joel Rybicki
8

Também para gráficos de largura de clique limitada (que é mais geral que a largura da árvore): Kobler e Rotics .

nf(k)

Além disso, a largura da clique é difícil de calcular, mas existe um algoritmo de aproximação de Oum e Seymour, "aproximando a largura da clique e a largura da ramificação" (com aproximação exponencial).

k

Magnus Wahlström
fonte
8

Qualquer família de gráficos com largura de árvore limitada terá um algoritmo de tempo polinomial para calcular o número cromático. Gamarnik reduz o problema de contar cores ao problema de calcular marginais de certos campos aleatórios de Markov definidos no mesmo gráfico. O resultado segue porque os marginais de MRFs em gráficos de largura de árvore limitada podem ser calculados em tempo polinomial com o algoritmo de árvore de junção .

Atualização 8/26 : Aqui está um exemplo de "# de corantes" <-> redução de margens. É necessário começar com uma coloração adequada, que pode ser encontrada em tempo polinomial para gráficos de largura de árvore limitada com a versão max-plus do algoritmo de árvore de junção. Agora, pensando bem ... você realmente não precisa de # de corantes para número cromático, apenas uma única coloração adequada

Yaroslav Bulatov
fonte
6

P5C5P5

2P3

Também existem resultados de Daniel Marx em relação à complexidade do problema dos números cromáticos em gráficos que podem ser feitos cordais por no máximo k deleções de vértices; para cada k corrigido, esse problema é polinomial ( http://dx.doi.org/10.1016/j.tcs.2005.10.008 ).

Bart Jansen
fonte
Obrigado! Estas referências parecem bastante interessante (em particular, o papel "Decidir k-de coloração de grafos P5-livres no polinomial).
Joel Rybicki
4

Algoritmos para colorir quadríceps .
M. Bern, D. Eppstein e B. Hutchings.
http: // arXiv: cs.CG/9907030 .
Algorithmica 32 (1): 87-94, 2002.

Consideramos várias variações do problema de colorir os quadrados de uma quadtree, de modo que não haja dois quadrados adjacentes iguais. Fornecemos algoritmos de tempo linear simples para quadríceps balanceados de 3 cores com adjacência de arestas, quadríceps desbalanceados de 4 cores com adjacência de arestas e quadríceps balanceados ou desequilibrados de 6 cores com adjacência de cantos. O número de cores usadas pelos dois primeiros algoritmos é ideal; para o terceiro algoritmo, às vezes podem ser necessárias cinco cores.

Aryabhata
fonte