Auf welchen Klassen von Graphen ist RCSP (Resource Constrained Shortest Path) NP-hart?

Ich möchte ein Problem, an dem ich arbeite, mit einem bekannten NP-harten Problem verknüpfen. Ich denke, ich kann mein Problem als ein Problem mit ressourcenbeschränkten kürzesten Pfaden modellieren. Die Struktur meines Graphen ist jedoch nicht völlig willkürlich. Daher ist es hilfreich zu wissen, wann RCSP schwierig wird. Ist es schwierig für eine DAG, für eine planare DAG, für eine DAG mit begrenztem Abschluss? Jede Hilfe wäre sehr dankbar!

Ich weiß nicht, ob Sie noch an dieser (alten) Frage interessiert sind und ob ich die Ressourcenbeschränkungen, die Sie in dem Kommentar angegeben haben, gut verstanden habe. Es scheint jedoch, dass Ihr Problem (das sich geringfügig von den üblichen RCSP-Problemen unterscheidet) für planare (ungerichtete oder gerichtete oder gerichtete azyklische) Graphen mit maximalem Grad 3 NP-vollständig ist .

Die einfache Reduzierung erfolgt ab 3-SAT. Bei gegebener Formel mit Variablen und Klauseln :$\varphi$$n$$x_1,...x_n$$m$$C_1,...C_m$

• Sie eine Ressourcenbeschränkungsmenge mit zwei Eckpunkten für jedes positive Literal in und eine Ressourcenbeschränkungsmenge mit zwei Eckpunkten für jedes negative Literal in ; x k$M_k^+$$x_k$$\varphi$$M_k^-$$\bar{x}_k$$\varphi$
• Beginnen Sie mit der Erstellung eines Graphen aus einem Quellknoten und teilen Sie für jede Variable x i den Pfad in zwei Zeilen auf : Die obere durchläuft einen Scheitelpunkt aller M - k , die einem negativen Literal ˉ x k entsprechen . der untere durchquert einen Scheitelpunkt aller M + k , die einem positiven Literal x k entsprechen ;$s$$x_i$$M_k^-$$\bar{x}_k$$M_k^+$$x_k$
• dann teilen Sie für jedes den Pfad in 3 Linien, die parallel die 3 Eckpunkte durchlaufen, die den Literalen von C j entsprechen und die aus dem entsprechenden M + k oder M - k ausgewählt werden ;$C_j$$C_j$$M_k^+$$M_k^-$
• Fügen Sie schließlich einen Senkenknoten .$t$

Ein Pfad von nach t existiert genau dann, wenn die ursprüngliche Formel erfüllt werden kann (dh ohne Verlust der Allgemeinheit können Sie nach einem Pfad der Länge ≤ | V | fragen ).$s$$t$$\leq |V|$

Informell müssen Sie beim Durchlaufen des Variablenabschnitts , wenn Sie die obere Zeile auswählen ( wahre Zuweisung), einen der Scheitelpunkte aller M - k- Ressourcenbeschränkungssätze "verwenden" , die auch einen Scheitelpunkt enthalten, der später zum Durchlaufen verwendet werden kann (erfüllen) eine Klausel, die ˉ x i enthält . Wenn Sie die untere Zeile auswählen ( falsche Zuweisung), müssen Sie einen der Scheitelpunkte aller M + k- Ressourcenbeschränkungssätze "verwenden" , die auch einen Scheitelpunkt enthalten, der später verwendet werden kann, um eine Klausel mit x i zu durchlaufen (zu erfüllen)$x_i$$M_k^-$$\bar{x}_i$$M_k^+$$x_i$. Beim Durchlaufen jeder Klausel muss mindestens einer der drei Eckpunkte in einem , das noch nicht "verwendet" wurde (dh mindestens einer von ihnen kann verwendet werden, um die Klausel zu erfüllen).$M_k$

Die folgende Abbildung soll die Reduzierung klarer machen. Die Ressourcenbeschränkungssätze werden mit unterschiedlichen Farben dargestellt (und für jede Farbe gibt es genau 2 Eckpunkte).$M_k$

$C_1 = x_1 \lor \bar{x}_2 \lor x_3$
$C_2 = x_2 \lor \bar{x}_3 \lor x_4$
$C_3 = \bar{x}_1 \lor x_3 \lor \bar{x}_2$

Sie können den Graphen auch leicht gerichtet, azyklisch und zweigeteilt machen. Lassen Sie mich wissen, wenn Sie weitere Details benötigen (oder wenn ich das Problem völlig falsch verstanden habe :-).

$k$