Ist das Problem mit dem längsten Pfad einfacher als das Problem mit dem längsten Pfad?

14

Das Problem mit dem längsten Pfad ist NP-schwer. Der (typische?) Beweis beruht auf einer Reduktion des Hamiltonschen Pfadproblems (das NP-vollständig ist). Beachten Sie, dass hier der Pfad als (knoten-) einfach angesehen wird. Das heißt, kein Scheitelpunkt kann mehr als einmal im Pfad auftreten. Offensichtlich ist es also auch kantenschonend (keine Kante wird mehr als einmal im Pfad auftreten).

Was ist also, wenn wir die Anforderung, einen (knoten-) einfachen Pfad zu finden, fallen lassen und bei der Suche nach einem kanten-einfachen Pfad (Trail) bleiben. Auf den ersten Blick könnte man hoffen, dass es einfacher ist, den längsten Weg zu finden, als den längsten Weg. Ich kann jedoch keine Referenz finden, die dies beweist, geschweige denn eine, die einen Algorithmus liefert.

Beachten Sie, dass mir das hier vorgebrachte Argument bekannt ist scheint in seiner aktuellen Form fehlerhaft zu sein, da es im Grunde zeigt, dass Sie den kanten-einfachen Fall lösen können, indem Sie den knoten-einfachen Fall in einem anderen Diagramm lösen (die Reduktion ist also falsch herum). Es ist nicht klar, dass die Reduzierung leicht geändert werden könnte, um auch in die andere Richtung zu arbeiten. (Dennoch zeigt es, dass zumindest das Problem mit den längsten Pfaden nicht schwerer ist als das Problem mit den längsten Pfaden.)

Gibt es bekannte Ergebnisse für die Suche nach den längsten Pfaden (randlose Pfade)? Komplexität (Klasse)? (Effizienter) Algorithmus?

graph-theory graph-algorithms hamiltonian-paths Jaspis
quelle
Dies ist nicht genau dasselbe Problem, aber werfen Sie einen Blick auf das ähnlichste Problem der Minimum Euilerian Extension.
RB
10
Vielleicht habe ich die Frage nicht gut verstanden, aber der Hamilton-Pfad ist auch in kubischen Graphen NP-vollständig, da für jede Durchquerung eines Knotens zwei Kanten erforderlich sind. Es gibt keine Möglichkeit, einen Knoten zweimal wiederzuverwenden, selbst wenn wir die Bedingung von knoten-einfach lockern Pfade zu randlosen Pfaden; Das Hamiltonsche Pfadproblem bleibt also NP-vollständig.
Marzio De Biasi
3
@Bangye: ok, aber in kubischen Graphen müssen 2 Kanten verwendet werden, wenn ein Knoten einmal überquert wird ... und der Knoten kann nicht erneut überquert werden (da es nur eine nicht überquerte Kante gibt). In kubischen Graphen können die Knoten nicht "wiederholt" werden (mit Ausnahme der letzten Kante des Pfades, die auf einen bereits durchquerten Knoten fallen kann)
Marzio De Biasi
1
Hier ist die Referenz: AA Bertossi, Das Rand-Hamilton-Pfad-Problem ist NP-vollständig, Information Processing Letters, 13 (1981) 157-159.
Lamine
1
@Lamine: Danke für die Klarstellung. Ich glaube nicht, dass Sie Ihre Kommentare löschen müssen, da es sehr natürlich wäre, zuerst eine ähnliche Idee zu entwickeln und zu sehen, dass sie nicht funktioniert, ist sehr hilfreich.
Yota Otachi

Antworten:

21

Aus den obigen Kommentaren geht hervor, dass das Hamilton-Zyklus-Problem auch in Gittergraphen mit maximalem Grad 3 [1] NP-vollständig bleibt. In diesen Graphen sind jedoch für jede Durchquerung eines Knotens zwei Kanten erforderlich und höchstens eine Kante bleibt ungenutzt, sodass ein Knoten nicht verwendet werden kann zweimal von einem eulerschen Pfad durchquert.

Es gibt also anscheinend eine unmittelbare Reduktion vom Hamiltonschen Zyklusproblem auf Ihr Problem: Wenn Sie ein Gitterdiagramm mit maximalem Grad 3 , fragen Sie einfach nach einer Spur der Länge | V | .G=(V,E)|V|

Es können jedoch alle drei Kanten des Knotens am Ende des Pfades verwendet werden. Um diese Situation zu vermeiden, können Sie den oberen linken Knoten des Gittergraphen (der Grad zwei hat) auswählen und zwei Knoten hinzufügen: V ' = V ∪ { u ' , u ″ } und eine neue Kante E = E ∪ { ( u , u ′ ) , ( u , u ″ ) } und frage nach einer Spur der Länge | V ' | = | V | +uV′=V∪{u′,u″}E=E∪{(u,u′),(u,u″)} : informell die addierten Kantenkräfte u ' , u " die Endpunkte der Spur zu sein.|V′|=|V|+2u′,u″

[1] Christos H. Papadimitriou, Umesh V. Vazirani, Zu zwei geometrischen Problemen im Zusammenhang mit dem Problem des Handlungsreisenden, Journal of Algorithms, Band 5, Ausgabe 2, Juni 1984, Seiten 231-246, ISSN 0196-6774

Marzio De Biasi
quelle
Ich habe ein wenig Probleme, dies und einige der anderen Kommentare mit der bekannten Leichtigkeit zu verbinden, einen Euler-Pfad zu finden. Oder ist es der entscheidende Punkt, der (an Ihrem Beispiel festhält) darüber entscheidet, ob es eine "Euler'sche" Spur der Länge gibt oder nicht ist einfacher , als ob es eine Spur der Länge der Entscheidung ist | V | ? Das wäre sicherlich eine kleine Überraschung für mich, aber auf jeden Fall interessant. |E||V|
Jasper
1
|E|O(1)|V|u′,u″
Marzio De Biasi