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.
cc.complexity-theory
graph-theory
Florent Foucaud
źródło
źródło
Odpowiedzi:
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 | miG = ( V, E) sol′= ( V∪ U, E′) sol U .| U| =3 | mi|
Wykres jest dwustronny. Ponadto, jeśli G jest płaski i ma max. stopień 3, a następnie Gsol′ sol jest również płaski i ma max. stopień 3.sol′
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 ′re′ sol′ (x,y)∈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 za∈D′ c∈D′ c i dodajD′ do D ' . Stąd wlog mamy | D ′ ∩ U | = | E | .y D′ |D′∩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′∩V x∈V x∉D′ a∈D′ (x,a)∈E′ (x,y)∈E (x,a,b,c,y) G′ . Od i a ∈ D ′ , mamy b , c ∉ D ′a , b , c ∈ U a ∈ D′ b , c ∉ 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 .do y∈D′ G y x y∈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 doD G D′ G′ |D′|=|D|+|E| (x,y)∈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 , żex∉D y∈D c D′ x∈D y∉D b D′ D′ G′ U x∈V∖D′ y∈V i stąd wzdłuż ścieżki ( x , , b , c , y ) mamy do ∈ D ' , który dominuje X .(x,y) ∈ E ( x , a , b , c ,y) a ∈ 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 .sol k sol′ k + | mi| sol′ k + | mi| sol 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.sol sol′ sol′
źródło