Einfacher Beweis für die NP-Vollständigkeit des Edge Dominating Set

In einem Diagramm ist eine kantendominierende Menge eine Teilmenge D der Kanten, sodass sich jede Kante im Diagramm entweder in D befindet oder einen Endpunkt mit einer Kante in D teilt. Das Problem der minimalen kantendominierenden Menge besteht darin, eine kantendominierende Menge zu finden der minimalen Kardinalität. Die Entscheidungsversion dieses Problems ist bekanntermaßen NP-vollständig, aber ich möchte fragen, ob ein relativ einfacher Beweis für diese Tatsache bekannt ist.

Der einzige Beweis, den ich in der Literatur gefunden habe, ist das Papier von Gavril und Yannakakis , das sich zuerst mit diesem Problem befasste . Der obige Beweis nutzt jedoch die Tatsache, dass Vertex Cover für planare kubische Graphen NP-vollständig ist, und die Tatsache, dass zweigeteilte Graphen vom Grad d d-kantenfarben sein können. Ich würde einen einfacheren Beweis bevorzugen, der nur Fakten verwendet, die normalerweise Studenten bekannt sind, die einen Algorithmuskurs belegt haben.

Ich gehe davon aus, dass Sie nur zeigen möchten, dass das Problem der minimalen kantendominierenden Menge für das allgemeine Diagramm NP-vollständig ist (dh es ist Ihnen egal, welche Eigenschaften das konstruierte Diagramm hat).

Falls Sie es verpasst haben, gibt es im selben Artikel eine wohl einfachere Reduktion von 3-SAT (siehe Satz 2). Die Reduzierung setzt kein weiteres "Fachwissen" voraus. Sie können die Darstellung noch etwas vereinfachen, indem Sie die Überprüfung der Zweiteiligkeit und Begrenztheit des maximalen Grades des resultierenden Diagramms überspringen.

Es gibt eine einfache Verringerung der Papierannäherungshärte von kantendominierenden Mengenproblemen (Chlebík und Chlebíková, Journal of Combinatorial Optimization 11 (3): 279–290, 2006).

Die Reduzierung besteht darin, einen universellen Scheitelpunkt hinzuzufügen, der mit allen Knoten verbunden ist, und jede Kante durch a zu ersetzen $P_5$mit einer hängenden Kante zum mittleren Scheitelpunkt hinzugefügt. Es gibt eine Kante, die die Größe dominiert$|E|+k$ In der neuen Grafik gibt es eine Scheitelpunktabdeckung der Größe $k$im Original. Sie benötigen mindestens eine Kante für jedes Gadget. der Rest ist klassisch. (Eigentlich denke ich, dass Sie den universellen Scheitelpunkt nicht brauchen)

Wir werden Vertex Cover auf Edge Dominating Set reduzieren und den Proof vervollständigen. Gegeben eine Instanz der Entscheidungsversion des Vertex-Cover-Problems$I(G,k)$wir konstruieren $G'$ beim Hinzufügen $nk+k$ neue Kanten zu $G$, wo $n$ ist die Anzahl der Eckpunkte in $G$::

• hinzufügen $k$ neue Eckpunkte;
• Fügen Sie eine Kante zwischen jedem dieser neuen Scheitelpunkte und jedem Scheitelpunkt in hinzu $G$, total $nk$ Kanten, sogenannte Zwischenkanten;
• Fügen Sie jedem der neuen Scheitelpunkte eine hängende Kante hinzu $k$ Kanten.

Beachten Sie, dass die dominierende Kante einsetzt $G'$ enthält mindestens $k$Kanten. Beachten Sie auch, dass jede Kante einen Satz von Größen dominiert$k$ im $G'$kann nur Zwischenkanten enthalten. Dann behaupten wir das$G$ hat eine Scheitelabdeckung von Größe $k$ iff $G'$ hat eine Kante, die die Größe dominiert $k$.