Algoritmos de espaço de log em gráficos com largura de árvore delimitada

A largura da árvore mede a distância entre um gráfico e uma árvore. É NP-difícil calcular a largura da árvore. O algoritmo de aproximação mais conhecido atinge fator. $O(\sqrt{{\log}n})$

O teorema de Courcelle afirma que qualquer propriedade dos gráficos definíveis na lógica monádica de segunda ordem (MSO2) pode ser decidida em tempo linear em qualquer classe de gráficos com largura de árvore delimitada . Um artigo recente mostrou que o teorema de Courcelle ainda é válido quando "tempo linear" é substituído por "espaço de registro". No entanto, isso não resolve a complexidade espacial do isomorfismo de gráfico em gráficos com largura de árvore delimitada. O resultado mais conhecido o coloca no LogCFL.

Existem outros problemas que são:

NP-rígido (ou não conhecido em P) em gráficos gerais, e
conhecido por ser solucionável em tempo linear / polinomial em gráficos com largura de árvore delimitada, e
NÃO é conhecido por estar no LogSpace?

cc.complexity-theory ds.algorithms graph-theory space-bounded treewidth Shiva Kintali
fonte

Qual é o

mencionado no fator de aproximação?

n

$n$

gphilip

é o número de vértices no gráfico de entrada.

n

$n$

Shiva Kintali

Em geral, podemos fazer melhor que

na aproximação da largura da árvore. O melhor algoritmo de aproximação de tempo polinomial que eu conheço atinge um

O (\sqrt{\log n})

$O(\sqrt{\log n})$

fator de aproximação, onde

é a largura da árvore do gráfico. Veja Feige, Hajiaghayi e Lee,algoritmos de aproximação aprimorados para separadores de vértices de peso mínimo, STOC 2005.

O (\sqrt{\log w})

$O(\sqrt{\log w})$

w

$w$

gphilip

Respostas:

O polinômio tutte é um exemplo.

Essa é uma generalização do polinômio cromático , que por si só é um problema difícil de P em qualquer formulação razoável. Em

Avaliando o polinômio de Tutte para gráficos de largura de árvore delimitada , SD nobre, combinatória, probabilidade e computação, 1998,

$O(f(k)n^{4+\epsilon})$ $k$ $n$

Parece que o problema não pode ser expresso diretamente no MSO2, embora eu não esteja familiarizado com as definições detalhadas ... Espero que esse problema seja o que você precisa!

Hsien-Chih Chang 張顯之
fonte

Qual é a função f?

Michael Blondin

k

$k$

O (2^{(k^{3 + ϵ})})

$O(2^{(k^{3+\epsilon})})$

Makowski diz que "todos os polinômios de gráficos estudados na literatura são definíveis por SOL" e fornece uma formulação do polinômio de Tutte em termos de SOL, página 15 de "De um zoológico a uma zoologia: em direção a uma teoria geral dos polinômios de grafos". Em "Utilizações algorítmicas do teorema de Feferman-Vaught", ele estende o teorema de Courcelle para mostrar a tratabilidade de polinômios definíveis por SOL em gráficos de largura de árvore limitada.

Yaroslav Bulatov