Aproximación del problema de género

¿Qué se sabe actualmente sobre la aproximabilidad del problema del género? Una búsqueda preliminar me dice que una aproximación de factor constante es trivial para gráficos suficientemente densos, y se ha descartado un algoritmo de aproximación . ¿Esta información está actualizada o se conocen mejor límites?$n^\epsilon$

Los mejores resultados publicados aparecen en un artículo de 1997 de Jianer Chen, Saroja P. Kanchi y Arkady Kanevsky.

• Para cualquier fijo > 0 , calcular el género de un gráfico con error aditivo O ( n ε ) es NP-hard.$\varepsilon>0$$O(n^\varepsilon)$

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

• $O(\sqrt{n})$

Es una pregunta abierta si existe un algoritmo eficiente de aproximación de factor constante.

Quería agregar a la respuesta integral de Jɛ ff E que, a mi leal saber y entender, no hay límites inferiores en el factor de aproximación para este problema. Hasta donde sabemos, puede haber un algoritmo de aproximación que siempre proporcione una aproximación de factor constante (incluso si el género es muy pequeño).

$O(n^{1-\varepsilon})$$G$$\mathrm{genus}(G) \leq g^*$$\mathrm{genus}(G) \geq g^*+1$$g^*$$n$$G$$k$$N = n^k$$G$$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^*$