Expressões de largura de clique com profundidade logarítmica

15

Quando recebemos uma decomposição em árvore de um gráfico com largura , existem várias maneiras pelas quais podemos torná-lo "agradável". Em particular, sabe-se que é possível transformá-lo em uma decomposição de árvore onde a árvore é binária e sua altura é . Isso pode ser conseguido mantendo a largura da decomposição no máximo . (Veja, por exemplo, "Algoritmos paralelos com aceleração ideal para largura de árvore limitada", por Bodlaender e Hagerup). Portanto, a profundidade logarítmica é uma propriedade de uma decomposição de árvore que podemos obter quase de graça.GwO(logn)3w

Minha pergunta é se existe um resultado semelhante para a largura de clique, ou talvez um contra-exemplo. Em outras palavras, dada uma expressão de largura de clique para usando rótulos, sempre existe uma expressão de largura de clique de altura para , que usa no máximo rótulos ? Aqui, a altura é definida naturalmente como a altura da árvore de análise da expressão de largura de clique.GkO(logn)Gf(k)

Se uma declaração semelhante à acima não for conhecida, existe um exemplo de um gráfico -vertex com pequena largura de clique , de modo que a única maneira de construir com rótulos é usar uma expressão com letras grandes profundidade?nGkGf(k)

Michael Lampis
fonte

Respostas:

5

Depois de um tempo, encontrei uma resposta na literatura, por isso estou publicando aqui, caso seja útil para outra pessoa.

De fato, é possível reequilibrar expressões de largura de clique para que elas tenham profundidade logarítmica. O resultado é apresentado no artigo "Operações gráficas que caracterizam a largura da classificação e as expressões gráficas balanceadas" de Courcelle e Kanté, WG '08. Cito o Teorema 4.4 do artigo:

"Todo gráfico de largura de clique ou largura de NLC é o valor de uma expressão de largura de clique equilibrada em 3 de largura de clique ou largura de NLC no máximo k × 2 k + 1 "kk×2k+1

O problema aqui é que o número de etiquetas explode exponencialmente no balanceamento. Parece que, para largura de clique, nenhum resultado melhor é conhecido atualmente. O mesmo artigo fornece um resultado semelhante, com apenas um aumento constante da largura de classificação, mas isso não ajuda, pois a diferença entre largura de clique e largura de classificação pode ser exponencial no pior dos casos.

Michael Lampis
fonte
3
O primeiro resultado que lida com expressões balanceadas de largura de clique é de Courcelle e Vanicat (DAM 131 (1): 129-150, 2003). O artigo WG'07 generaliza as técnicas do artigo 2003 e fornece condições suficientes para que uma álgebra de gráfico obtenha expressões equilibradas. Minha hipótese era que não podemos evitar a explosão exponencial, mas nunca tento provar ou refutar. Pelo menos nossa técnica não pode evitar a explosão exponencial.
M. kanté