Um algoritmo exato para biclique-coloração

• Guilherme de C. M. Gomes UFMG
• Vinicius Fernandes dos Santos UFMG

DOI: https://doi.org/10.5753/etc.2017.3183

Resumo

O número biclique-cromático X_B(G) de um grafo G = (V, E) é o menor inteiro k tal que existe uma k-coloração dos vertices de G com a propriedade de que nenhuma biclique maximal de G seja monocromática. Trabalhos recentes provaram que o problema de se computar X_B(G) para um grafo G é ∑^p₂-completo para qualquer k ≥ 2. Nosso principal resultado neste trabalho é um algoritmo baseado em inclusão-exclusão de complexidade O*(2ⁿ) para se computar X_B(G) de forma exata.

Referências

Björklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM Journal on Computing 39(2), 546–563 (2009)

Cochefert, M., Kratsch, D.: Exact algorithms to clique-colour graphs. In: International Conference on Current Trends in Theory and Practice of Informatics. pp. 187–198. Springer (2014)

Gaspers, S.: Exponential Time Algorithms. Serge Gaspers (2010)

Groshaus, M., Soulignac, F.J., Terlisky, P.: Star and biclique coloring and choosability. Journal of Graph Algorithms and Applications 18(3), 347–383 (2014)

Koivisto, M.: An o*(2ˆ n) algorithm for graph coloring and other partitioning problems via inclusion–exclusion. In: Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on. pp. 583–590. IEEE (2006)

Macêdo Filho, H., Machado, R., de Figueiredo, C.: Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs. Algorithmica pp. 1–29 (2016)

Marx, D.: Complexity of clique coloring and related problems. Theoretical Computer Science 412(29), 3487–3500 (2011)