NP-Härte beim Finden einer Teilmenge von Eckpunkten in einem scheitelpunktgewichteten Graphen

8

Dies ist eine Aufgabe des Bundeswettbewerb Informatik, aber da die Frist abgelaufen ist, ist es kein Betrug, diese Frage zu stellen.

Finden Sie bei einem , gerichteten Graphen und den Werten eine Teilmenge der Knoten V_ {res} \ subseteq V , die \ sum_ {v \ in V_ {res}} c_v maximiert, vorbehaltlich \ forall ( u, v) \ in E: u \ in V_ {res} \ impliziert v \ in V_ {res} Ist dieses Problem NP-schwer?G=(V,E)cvVres⊆V

∑v∈Vrescv
∀(u,v)∈E:u∈Vres⟹v∈Vres

Ich konnte beweisen, dass das Problem in P liegt, wenn jeder Knoten entweder keine Eltern oder keine Kinder hat, indem ich zeigte, dass es in diesem Fall durch Vertex Cover auf zweigeteilten Graphen gelöst werden kann, aber ich konnte keine Reduktion finden, die die NP-Härte belegt des ursprünglichen Problems.

Kann mir jemand einen Hinweis geben, wie das geht?

PS: Im Wettbewerb bestand die Aufgabe nur darin, einen Algorithmus zu finden, der dieses Problem löst. Die ursprüngliche (deutsche) Definition ist Aufgabe 1 dieses Dokuments: http://www.bundeswettbewerb-informatik.de/fileadmin/templates/bwinf/ aufgaben / bwinf35 / aufgaben352.pdf

complexity-theory reductions np-hard Feanor
quelle
5
Ohne Verlust der Allgemeinheit können Sie sich auf den Fall eines Dags konzentrieren (gerichteter azyklischer Graph). Zerlegen Sie in einem allgemein gerichteten Graphen in stark verbundene Komponenten. Dann nehmen Sie entweder alle Knoten in einer Komponente oder keinen von ihnen. So können Sie das Meta-Diagramm (mit einem Scheitelpunkt pro Komponente) erstellen und das Problem im Meta-Diagramm lösen.
DW
@DW, ich gehe davon aus, dass Sie beabsichtigen, die DAG topologisch zu sortieren, aber mir ist nicht klar, wie genau Ihr nächster Schritt aussehen wird. Für jeden Scheitelpunkt im Metadiagramm, um das Gewicht aller seiner Verstorbenen zu summieren?
Eric_
@Eric_, leider habe ich keinen nächsten Schritt im Sinn. Ich sage nur, wenn Sie einen Algorithmus finden, um dies für eine beliebige DAG zu lösen, können Sie diesen verwenden, um ihn für einen beliebigen gerichteten Graphen zu lösen. Vielleicht gibt das jemandem einige Ideen, wie er das Problem angehen kann - oder vielleicht auch nicht. Ich fürchte, ich weiß nicht, wie ich es selbst lösen soll.
DW

Antworten:

1

Das Problem ist in Polynomzeit lösbar, wie in Lemma 1 des Papiers Computational Complexity of Some Maximum Average Weight Problems mit Prioritätsbeschränkungen vorgeschlagen .

Grundsätzlich ist die Idee, ein lineares Programm zu schreiben , auf Variable , wobei , wenn . Die vorzeichenbehaftete Adjazenzmatrix ist völlig unimodular, sodass wir das integrale Optimum berechnen können.xi∈[0,1]xu−xv≤0(u,v)∈E

Willard Zhan
quelle