Aproximabilidade do problema de gênero

O que se sabe atualmente sobre a aproximabilidade do problema de gênero? A pesquisa preliminar me diz que um fator de aproximação constante é trivial para gráficos suficientemente densas, e um $n^\epsilon$ -approximation algoritmo foi descartada. Essas informações estão atualizadas ou existem limites melhores?

Os melhores resultados publicados aparecem em um artigo de 1997 de Jianer Chen, Saroja P. Kanchi e Arkady Kanevsky.

• Para qualquer fixo > $\varepsilon>0$ , calcular o gênero de um gráfico com erro aditivo $O(n^\varepsilon)$ é NP-difícil.

• $n$$g$$\max\{4g, g+4n\}$

• Existe um algoritmo de aproximação de tempo polinomial para gráficos de graus limitados.$O(\sqrt{n})$

É uma questão em aberto se existe um algoritmo eficiente de aproximação de fator constante.

Eu queria acrescentar à resposta abrangente de Jɛ ff E que, de acordo com o meu conhecimento, não há limites inferiores no fator de aproximação para esse problema. Até onde sabemos, pode haver um algoritmo de aproximação que sempre fornece uma aproximação constante de fatores (mesmo que o gênero seja muito pequeno).

O artigo Chen, Kanchi e Kanevsky [CKK '97] apenas diz que computar o gênero com erro aditivo é NP-difícil. Aqui está um esboço muito informal de seu argumento. Ficará claro que esse argumento não pode ser usado para provar um limite inferior no fator de aproximação. Considere um gráfico tal que seja NP-difícil determinar se ou (para alguns ) ; esse gráfico existe, pois o problema é difícil de NP. Deixe que seja o número de vértices em . Seja uma constante grande. Pegue cópias separadas do gráfico$O(n^{1-\varepsilon})$$G$$\mathrm{genus}(G) \leq g^*$$\mathrm{genus}(G) \geq g^*+1$$g^*$$n$$G$$k$$N = n^k$$G$e considere sua união. Então, no gráfico obtido , é NP difícil determinar se ou . Ou seja, é NP difícil calcular com erro aditivo , em que . Essa construção não nos dá nenhum limite inferior ao fator de aproximação; a razão de para é igual à razão de para .$G'$$\mathrm{genus}(G') \leq N g^*$$\mathrm{genus}(G') \geq N(g^*+1)$$\mathrm{genus}(G')$$N = (Nn)^{k/{k+1}} = |V(G')|^{k/{k+1}} = |V(G')|^{1-\varepsilon}$$\varepsilon = 1/(k+1)$$N(g^*+1)$$Ng^*$$g^*+1$$g^*$