Le problème de définition du sommet de rétroaction est-il difficile sur les graphiques de degrés bornés

Est-il connu si le problème posé par le sommet de rétroaction sur les graphes planaires non orientés de degré borné est dur?$\mathsf{NP}$

Selon le livre de Garey et Johnson, Vertex Cover est NP-complet sur les graphiques planaires de degré quatre maximum. L'utilisation d'une simple réduction de Vertex Cover à Feedback Vertex Set devrait donner un degré maximum de huit et préserver la planéité.

VC à FVS: remplacez chaque bord par un triangle (ou un double bord).

Une remarque: Garey et Johnson affirment également que le FVS dirigé est NP-complet sur les digraphes planaires sans degré d'entrée ou de sortie supérieur à deux. Ils ne mentionnent pas spécifiquement les FVS non dirigés sous de telles restrictions.

$4$

$4$

La contrainte de degré est la meilleure possible, car FVS est polynomial pour les graphiques de degré maximum au plus trois; voir ici .

Edit: les graphclasses.org d' Ernst de Ridder contiennent désormais toutes les informations disponibles sur FVS; y compris environ 550 boîtiers solvables polynomialement et environ 250 boîtiers NP-c.

Selon Wikipédia, Garey & Johnson a également montré que "la couverture de sommet reste NP-complète ... même dans les graphiques plans de degré au plus 3".

Ainsi, FVS est difficile sur les graphes planaires avec un degré maximum 6.

Apparemment, dans la thèse de doctorat de Speckenmeyer, il démontre que le problème d'ensemble de vertex de rétroaction est NP-difficile pour les graphiques de degré maximum 4. Cette affirmation apparaît ici , par exemple.

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

Edit: n'a pas examiné l'édition de vb le avec suffisamment d'attention ...