Czy dominujący problem z zestawem jest ograniczony do płaskich dwustronnych grafów o maksymalnym stopniu NP-3?

Czy ktoś wie o wyniku NP-kompletności dla problemu ZESTAW DOMINUJĄCY na wykresach, ograniczonego do klasy płaskich dwustronnych grafów o maksymalnym stopniu 3?

Wiem, że jest NP-kompletny dla klasy grafów płaskich o maksymalnym stopniu 3 (patrz książka Gareya i Johnsona), a także dla grafów dwustronnych o maksymalnym stopniu 3 (patrz M. Chlebík i J. Chlebíková, „Twardość aproksymacyjna z dominujące problemy zadane na wykresach z ograniczonymi stopniami ”), ale nie udało się znaleźć kombinacji tych dwóch w literaturze.

Co jeśli po prostu wykonasz następujące czynności: Biorąc pod uwagę wykres , skonstruuj kolejny wykres G ′ = ( V ∪ U , E ′ ) , dzieląc każdą krawędź G na 4 części; tutaj U to zestaw nowych węzłów, które wprowadziliśmy, oraz | U | = 3 | $G = (V,E)$$G' = (V \cup U, E')$$G$$U$.$|U| = 3|E|$

Wykres jest dwustronny. Ponadto, jeśli G jest płaski i ma max. stopień 3, a następnie $G'$$G$ jest również płaski i ma max. stopień 3.$G'$

Niech będzie (minimalnym) dominującym zbiorem dla G ' . Rozważmy krawędź ( x , y ) ∈ E, która została podzielona w celu utworzenia ścieżki ( x , a , b , c , y ) w G ′ . Teraz wyraźnie przynajmniej jeden z a , b , c jest w D ' . Ponadto, jeśli mamy więcej niż jeden z a , b , c w D ′ D $D'$$G'$$(x,y) \in E$$(x,a,b,c,y)$$G'$$a,b,c$$D'$$a,b,c$$D'$ , to można zmodyfikować$D'$ aby pozostał prawidłowym zestawem dominującym, a jego rozmiar się nie zwiększał. Na przykład, jeśli mamy i C ∈ D ' , to równie dobrze można usunąć C z$a \in D'$$c \in D'$$c$ i dodaj$D'$ do D ' . Stąd wlog mamy | D ′ ∩ U | = | E | .$y$$D'$$|D' \cap U| = |E|$

Następnie rozważyć . Załóżmy, że x ∈ V i x ∉ D ′ . Musimy mieć węzła do ∈ D ", taki, że ( x , ) ∈ E ' . Stąd istnieje krawędź ( x , y ) ∈ E , takie, które ma ścieżki ( x , , b , c , y ), w G $D = D' \cap V$$x \in V$$x \notin D'$$a \in D'$$(x,a) \in E'$$(x,y) \in E$$(x,a,b,c,y)$$G'$ . Od i a ∈ D ′ , mamy b , c ∉ D $a,b,c \in U$$a \in D'$$b, c \notin D'$ , a aby zdominować , musimy mieć y ∈ D ′ . Tak więc, w G węzła Y jest sąsiadem x z y ∈ D . Oznacza to, że D jest zbiorem wyróżniającym dla G .$c$$y \in D'$$G$$y$$x$$y \in D$$D$$G$

Z drugiej strony, uważa się (co najmniej) zbiór dominujący do G . Zbuduj dominujący zestaw D ′ dla G ′ , aby | D ′ | = | D | + | E | w sposób następujący: Do krawędzi ( x , y ) ∈ E , który został podzielony w celu utworzenia ścieżki ( x , , b , c , r ), w G ' , dodajemy do$D$$G$$D'$$G'$$|D'| = |D| + |E|$$(x,y) \in E$$(x,a,b,c,y)$$G'$$a$$D'$ jeśli i y ∈ D ; dodajemy c do D ', jeżeli x ∈ D i y ∉ D ; a w przeciwnym razie dodajemy b do D ' . Teraz można sprawdzić, czy D ′ jest dominującym zestawem dla G ′ : Z założenia wszystkie węzły w U są zdominowane. Teraz niech x ∈ V ∖ D ′ . Potem jest takie y ∈ V , że$x \notin D$$y \in D$$c$$D'$$x \in D$$y \notin D$$b$$D'$$D'$$G'$$U$$x \in V \setminus D'$$y \in V$ i stąd wzdłuż ścieżki ( x , , b , c , y ) mamy do ∈ D ' , który dominuje X .$(x,y) \in E$$(x,a,b,c,y)$$a \in D'$$x$

Podsumowując, jeśli ma dominujący zestaw wielkości k , to G ′ ma dominujący zestaw wielkości co najwyżej k + | E | , a jeśli G ′ ma dominujący zestaw wielkości k + | E | , wówczas G ma dominujący zestaw wielkości co najwyżej k .$G$$k$$G'$$k + |E|$$G'$$k + |E|$$G$$k$

Edycja: Dodano ilustrację. U góry: oryginalny wykres ; środkowy: wykres G ′ z dominującym „znormalizowanym” zestawem; u dołu: wykres G ′ z dowolnym zbiorem dominującym.$G$$G'$$G'$