Ist das dominierende Mengenproblem auf planare zweigliedrige Graphen mit maximalem Grad 3 NP-vollständig beschränkt?

Kennt jemand ein NP-Vollständigkeitsergebnis für das DOMINATING SET-Problem in Graphen, die auf die Klasse der planaren zweigeteilten Graphen mit maximalem Grad 3 beschränkt sind?

Ich weiß, dass es NP-vollständig ist für die Klasse der planaren Graphen mit maximalem Grad 3 (siehe das Buch von Garey und Johnson) sowie für zweigliedrige Graphen mit maximalem Grad 3 (siehe M. Chlebík und J. Chlebíková, "Approximation hardness of dominierende Mengenprobleme in beschränkten Gradengraphen "), konnte aber in der Literatur die Kombination der beiden nicht finden.

Was ist, wenn Sie einfach Folgendes tun: Wenn Sie einen Graphen , konstruieren Sie einen weiteren Graphen G ' = ( V ∪ U , E ' ), indem Sie jede Kante von G in 4 Teile unterteilen; hier ist U die Menge der neuen Knoten, die wir eingeführt haben, und | U | = 3 | E | .$G = (V,E)$$G' = (V \cup U, E')$$G$$U$$|U| = 3|E|$

Der Graph ist zweiteilig. Wenn G eben ist und max. Grad 3, dann ist G ' auch planar und hat max. Grad 3.$G'$$G$$G'$

Sei eine (minimale) dominierende Menge für G ' . Man betrachte eine Kante ( x , y ) ∈ E , die unterteilt wurde, um einen Pfad ( x , a , b , c , y ) in G 'zu bilden . Nun ist klar, dass mindestens eines von a , b , c in D 'ist . Darüber hinaus können wir modifizieren , wenn wir mehr als eines von a , b , c in D ' haben$D'$$G'$$(x,y) \in E$$(x,a,b,c,y)$$G'$$a,b,c$$D'$$a,b,c$$D'$ so dass es eine gültige dominierende Menge bleibt und seine Größe nicht zunimmt. Wenn wir zum Beispiel ein ∈ D ' und ein c ∈ D ' haben , können wir c genauso gutaus D ' entfernenund y zu D ' addieren. Daher haben wir wlog | D ' ∩ U | = | E | .$D'$$a \in D'$$c \in D'$$c$$D'$$y$$D'$$|D' \cap U| = |E|$

Dann betrachten . Es sei angenommen, dass x ∈ V und x ∉ D ' . Dann müssen wir einen Knoten a ∈ D 'haben, so dass ( x , a ) ∈ E ' . Es gibt also eine Kante ( x , y ) ∈ E, so dass wir in G ' einen Pfad ( x , a , b , c , y $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'$. Da und a ∈ D ' , haben wir b , c ∉ D ' , und um c zu dominieren , müssen wir y ∈ D 'haben . Daher wird in G Knoten y ist ein Nachbar von x mit y ∈ D . Das heißt, D ist eine dominierende Menge für G .$a,b,c \in U$$a \in D'$$b, c \notin D'$$c$$y \in D'$$G$$y$$x$$y \in D$$D$$G$

Im Gegensatz dazu betrachten wir eine (Mindest-) Satz dominiert für G . Konstruiere eine dominierende Menge D ' für G ', so dass | D ' | = | D | + | E | wie folgt: Für eine Kante ( x , y ) ∈ E , die unterteilt wurde, um einen Pfad ( x , a , b , c , y ) in G 'zu bilden , addieren wir a zu$D$$G$$D'$$G'$$|D'| = |D| + |E|$$(x,y) \in E$$(x,a,b,c,y)$$G'$$a$ , wenn x ∉ D und y ∈ D ; wir addieren c zu D ', wenn x ∈ D und y ∉ D sind ; und sonst addieren wir b zu D ' . Nun kann überprüft werden, ob D ' eine dominierende Menge für G ' ist : Konstruktionsbedingt werden alle Knoten in U dominiert. Nun sei x ∈ V ∖ D ′ . Dann gibt es ein y ∈ V, so dass$D'$$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$ und damit entlang des Pfades ( x , a , b , c , y ) haben wir ein ∈ D ' , das x dominiert.$(x,y) \in E$$(x,a,b,c,y)$$a \in D'$$x$

Zusammenfassend gesagt, wenn eine dominierende Menge der Größe k hat , dann hat G ' eine dominierende Menge der Größe von höchstens k + | E | und wenn G ' eine dominierende Menge der Größe k + | hat E | , dann hat G eine dominierende Menge von Größen höchstens k .$G$$k$$G'$$k + |E|$$G'$$k + |E|$$G$$k$

Bearbeiten: Eine Illustration hinzugefügt. Oben: das Originaldiagramm ; Mitte: Graph G ' mit einer "normalisierten" dominierenden Menge; unten: Graph G ' mit einer beliebigen dominierenden Menge.$G$$G'$$G'$