Czy problem z ustawieniem wierzchołka sprzężenia zwrotnego na płaskich wykresach stopni jest trudny?

Czy wiadomo, czy problem z ustawieniem wierzchołka sprzężenia zwrotnego na niekierowanych grafach płaskich o ograniczonym stopniu jest twardy?$\mathsf{NP}$

Według książki Gareya i Johnsona Vertex Cover jest NP-kompletny na płaskich wykresach o maksymalnym stopniu czwartym. Używając prostej redukcji od osłony wierzchołka do sprzężenia zwrotnego, zestaw wierzchołków powinien dać maksymalny stopień osiem i zachować płaskość.

VC do FVS: Zastąp każdą krawędź trójkątem (lub podwójną krawędzią).

Jedna uwaga: Garey i Johnson stwierdzają również, że ukierunkowany FVS jest NP-kompletny na płaskich wykrojach, bez żadnego stopnia wejściowego lub wyjściowego przekraczającego dwa. W takich ograniczeniach nie wspominają wyraźnie o nieukierunkowanych FVS.

$4$

$4$

Ograniczenie stopnia jest najlepiej możliwe, ponieważ FVS jest wielomianem dla wykresów o maksymalnym stopniu co najwyżej trzech; patrz tutaj .

Edycja: graphclasses.org Ernsta de Riddera zawiera teraz wszystkie dostępne informacje o FVS; w tym około 550 przypadków rozwiązanych wielomianowo i około 250 przypadków NP-c.

Według Wikipedii Garey & Johnson wykazał również, że „pokrycie wierzchołków pozostaje NP-kompletne ... nawet na płaskich wykresach stopnia co najwyżej 3”.

Dlatego FVS jest trudny na wykresach płaskich z maksymalnym stopniem 6.

Widocznie, w pracy doktorskiej Speckenmeyer, on pokazuje, że zestaw problemem feedback wierzchołek jest NP-trudne dla wykresów stopniu maksymalnym 4. Twierdzenie to wydaje się tu , na przykład.

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

Edycja: nie zbadałem wystarczająco ostrożnie edycji vb le ...