Ist es NP-schwer, einen Pfad mit mehr roten als blauen Eckpunkten zu finden?

Wenn ein verbundener, gerichteter Graph , die Eckpunkte und eine Färbung, st und schwarz sind und alle anderen Eckpunkte entweder rot oder blau sind , ist es möglich, einen einfachen Pfad von zu finden bis mit mehr roten als blauen Eckpunkten in der Polynomzeit?$G=(V,E)$$s,t \in V$$s$$t$$s$$t$

Ich denke, es sollte möglich sein, aber unser TA sagte, dies sei NP-schwer.

Idee für eine Lösung:

Erstellen Sie aus wie folgt: $G$$G'=(V',E')$

• Teilen Sie alle in zwei Eckpunkte und . besteht aus den geteilten Scheitelpunktpaaren und und . $v \in V\setminus \{s,t\}$$v_{in}$$v_{out}$$V'$$s$$t$

• für alle eine Kante ein . (Für Kante oder wobei Kante bzw. .) Fügen Sie außerdem eine Kante für einen der geteilten Scheitelpunkte ein. So enthält zwei Arten von Kanten: diejenigen , die entsprechen den Kanten von und diejenigen , die entsprechen den Eckpunkten von .$e=(u,v) \in E$$(u_{out},v_{in})$$(x,v)$$(u,x)$$x \in \{s,t\}$$(x,v_{in})$$(u_{out},x)$$(v_{in},v_{out})$$E'$$E$$V$

Nun führen wir Gewichte wie folgt ein:

• $w((v_{in},v_{out})) = -1$ , wenn die entsprechenden Eckpunkt wurde rot . $v$
• $w((v_{in},v_{out})) = +1$ , wenn die entsprechenden Eckpunkt war blau . $v$
• $w(e) = 0$ für alle anderen Kanten, dh diejenigen, die Kanten von und nicht Eckpunkten entsprechen.$G$

Führen Sie nun einen Algorithmus für kürzeste Pfade Ihrer Wahl wie Dijkstra, Bellman-Ford, ... durch. Überprüfen Sie, ob die Länge des angegebenen Pfads und Sie sind fertig.$<0$

Warum geht das nicht? Liegt es daran, dass wir möglicherweise negative Zyklen haben? Wir könnten diejenigen mit Bellman Ford erkennen, aber dann müssten wir den gewünschten Weg mit nicht effizienten Mitteln finden, um dieses Entscheidungsproblem NP-schwer zu machen? Gibt es eine elegante Reduktion, um die NP-Härte zu zeigen?

Ihre Lösung funktioniert nicht, da Dijkstra und Bellman-Ford die Funktion "einfacher Pfad" nicht interpretieren können. Und sie werden in der Tat in jeden negativen Zyklus fallen.

Ich denke, das Beste, um die NP-Vollständigkeit zu zeigen, ist die Verwendung des Hamiltonschen Pfadproblems. Nehmen wir einen Graphen von roten Eckpunkten.$G'$$N$

Dann erstellen Sie einen Graphen und fügen , und blaue Eckpunkte hinzu . Sie verketten zuerst mit Kanten alle Blues-Eckpunkte von der Quelle bis zur letzten blauen ( -> -> -> ...-> ). Dann setzen Sie Kanten von auf jeden roten Scheitelpunkt und eine Kante von jedem roten Scheitelpunkt auf .$G$$s$$t$$N-1$$G'$$s$$b_1$$b_2$$b_{N-1}$$b_{N-1}$$t$

Ein einzelner Pfad von nach führt also notwendigerweise durch alle blauen Knoten ( ) und muss dann zu allen roten Knoten ( ) gehen, um darauf zu antworten$s$$t$$N-1$$N$

Gibt es in einen einfachen Pfad von nach mit mehr roten als blauen Eckpunkten?$G$$s$$t$

Das ist also wie eine Antwort auf:

Gibt es einen Hamilton-Pfad in$G'$

Ihr Problem ist also in der Tat NP-vollständig.