¿Es difícil el problema del vértice de retroalimentación en los gráficos de grado acotado plano?

¿Se sabe si el problema del conjunto de vértices de retroalimentación en gráficos planos no dirigidos de grado acotado es -hard?$\mathsf{NP}$

De acuerdo con el libro Vertex Cover de Garey y Johnson, se completa NP en gráficos planos de grado máximo cuatro. El uso de una reducción simple de la cubierta de vértices al conjunto de vértices de retroalimentación debería dar un grado máximo de ocho y preservar la planaridad.

VC a FVS: Reemplace cada borde por un triángulo (o un doble borde).

Una nota: Garey y Johnson también afirman que el FVS dirigido es NP-completo en los dígrafos planos sin un grado de entrada o salida superior a dos. No mencionan específicamente el FVS no dirigido bajo tales restricciones.

La respuesta es: FVS es NP-completo en gráficos planos no dirigidos de grado máximo ; probado por Speckenmeyer, ver aquí . Al subdividir cada borde por un nuevo vértice, se deduce fácilmente que$4$

FVS es NP-completo incluso en gráficos planos bipartitos no dirigidos de grado máximo .$4$

La restricción de grado es la mejor opción, ya que FVS es polinomial para gráficos de grado máximo como máximo tres; ver aquí .

Editar: Graphclasses.org de Ernst de Ridder ahora contiene toda la información disponible sobre FVS; incluyendo alrededor de 550 casos polinómicamente solubles y alrededor de 250 cajas NP-c.

Según Wikipedia, Garey & Johnson también mostró que "la cubierta del vértice sigue siendo NP completa ... incluso en gráficos planos de grado como máximo 3".

Por lo tanto, FVS es difícil en gráficos planos con un grado máximo de 6.

Aparentemente, en la tesis doctoral de Speckenmeyer, demuestra que el problema del conjunto de vértices de retroalimentación es NP-difícil para gráficos de grado máximo 4. Esta afirmación aparece aquí , por ejemplo.

$n/2-z(G)+1$$n$$z$$z(G)$$G$

Editar: no examinó la edición de vb le con suficiente cuidado ...