Axiome für kürzeste Wege

Angenommen, wir haben einen ungerichteten gewichteten Graphen (mit nicht negativen Gewichten). Nehmen wir an, dass alle kürzesten Pfade in eindeutig sind. Angenommen, wir haben diese -Pfade (Folgen ungewichteter Kanten), kennen aber selbst nicht. Können wir irgendein erzeugen , das diese Pfade als die kürzesten in der Polynomzeit gegeben hätte? Die schwächere Version: Können wir in polynomialer Zeit entscheiden, ob ein solches existiert? $G = (V, E, w)$ $G$ $\binom{n}{2}$ $G$ $G$ $G$

Die offensichtlich notwendige Bedingung ist die folgende: Für jedes Paar von Pfaden ist deren Schnittpunkt ebenfalls ein Pfad. Ist dieser Zustand ausreichend?

graph-theory co.combinatorics graph-algorithms metrics Ilyaraz
quelle

Ich muss über die Eingabe verwirrt sein: Wenn Sie in der Vereinigung der kürzesten Pfade zwei Eckpunkte

u, v

$u,v$ in einem Zyklus haben, dann gibt es zwei Pfade zwischen ihnen (die notwendigerweise die kürzesten sind), und einer muss von Ihnen kürzer als der andere sein Einzigartigkeitszustand

Suresh Venkat

@Suresh: Ich weiß nicht, worauf du Lust hast. Wenn der Graph G der vollständige Graph ist, ist der eindeutige kürzeste Pfad zwischen zwei Scheitelpunkten eine einzelne Kante, und die Vereinigung aller dieser kürzesten Pfade ist der vollständige Graph.

Tsuyoshi Ito

Ich denke, die Antwort lautet "Nein" für die Rekonstruktion eines gewichteten Graphen, da, wenn eine Kante in Ihrer Eingabe fehlt, es tatsächlich (a) in dem Graphen fehlen könnte oder (b) eine Kante mit einem wirklich sehr hohen Gewicht sein könnte. Ich finde die Version ohne Gewichte interessanter. Warum ist der Graph, den wir finden möchten, gewichtet und die Pfade, die wir erhalten, ungewichtet?

Artem Kaznatcheev

sei

H

$H$ die Vereinigung der kürzesten Wege. Gibt es einen Grund, warum

H

$H$ kein Graph ist, der dieselben kürzesten Pfade erzeugt? oder, mit anderen Worten, ist es nicht so, dass es keinen Graphen gibt, für den es sich um kürzeste Wege handelt , wenn die angegebenen kürzesten Wege nicht die kürzesten Wege in

H

$H$ sind?

Sasho Nikolov

@SashoNikolov Welche Gewichte sollen wir den Kanten zuweisen?

Ilyaraz

Antworten:

Ich bin gerade auf diese alte Frage gestoßen, als ich eine gezielte Suche durchgeführt habe, und ich habe kürzlich Antworten in diesem Artikel erhalten , die ich genauso gut teilen könnte. Ich hoffe, die Kombination von Threadnekromantie und Eigenwerbung ist verzeihlich.

Können wir irgendein G erzeugen, das diese Pfade als die kürzesten in der Polynomzeit gegeben hätte? Die schwächere Version: Können wir in polynomialer Zeit entscheiden, ob ein solches G existiert?

Die Antwort ist ja zu beiden. Mohammeds Algorithmus funktioniert auf jeden Fall, aber es gibt eine schnellere und direktere Methode, die das Ausführen von kubischen Trennorakeln überflüssig macht. Sei ein ungerichteter gewichteter Hilfsgraph, wobei die Gewichtung jeder Kante eine ganze Zahl ist, die angibt, wie viele der Pfade, die bei der Eingabe genommen werden, diese Kante enthalten. Betrachten Sie nun die kantenkapazitivierte Multicommodity-Flussinstanz über (Interpretieren von Kantengewichten als Kapazitäten), bei der das Ziel darin besteht, gleichzeitig eine Flusseinheit zwischen jedem Knotenpaar zu verschieben. Offensichtlich kann diese MC-Flussinstanz erfüllt werden, indem der Fluss auf natürliche Weise entlang der bei der Eingabe angegebenen Pfade verschoben wird. Wie sich herausstellt, kann man beweisen, dass wir uns für $H = (V, E, w')$ $e \in E$ $n \choose 2$ $H$ $n \choose 2$ Pfade sind genau dann eindeutige kürzeste Pfade in einigen wenn dies die eindeutige Methode ist, um die MC-Flussinstanz zu erfüllen. Wir können die Eindeutigkeit testen, indem wir eine LP aufbauen, deren Bedingungen die üblichen für die Durchführbarkeit des MC-Flusses sind, sowie eine bestimmte sorgfältig ausgewählte Zielfunktion, und die Kantengewichte eines erfüllenden können aus dem Dual dieser LP extrahiert werden. $G$ $G$

Die offensichtlich notwendige Bedingung ist die folgende: Für jedes Paar von Pfaden ist deren Schnittpunkt ebenfalls ein Pfad. Ist dieser Zustand ausreichend?

Diese Bedingung wird manchmal als "Konsistenz" bezeichnet (eine Reihe von Pfaden ist konsistent, wenn der Schnittpunkt von zwei beliebigen Pfaden jeweils ein Unterpfad ist). Daraus folgt, dass die Konsistenz nicht ausreicht. Eines der beiden kleinsten Gegenbeispiele ist das folgende farbcodierte System von vier Pfaden über sechs Knoten:

Mit anderen Worten, es gibt keine Möglichkeit, den hier abgebildeten 8 Kanten eine Gewichtung zuzuweisen, sodass alle diese vier Pfade gleichzeitig der eindeutige kürzeste Pfad zwischen ihren Endpunkten sind. Jedes Paar von ihnen schneidet sich jedoch auf nur einem Knoten, sodass sie konsistent sind (auch wenn wir sie mit ein paar zusätzlichen Pfaden auf die richtige Weise ausfüllen, damit insgesamt ). Es gibt unendlich viele Gegenbeispiele wie dieses; Eine Beschreibung finden Sie auf dem Papier. $n \choose 2$

Drei weitere kurze Kommentare zu all dem:

Die analogen Aussagen, die Sie vielleicht für alle erhoffen, sind in der Einstellung von gerichteten und nicht ungerichteten Diagrammen richtig.
Es gibt eine nette topologische Interpretation dieser Theorie, die zu zusätzlichen Einsichten und Intuitionen darüber führt, wie einzigartige kürzeste Pfade strukturiert werden können
Aus einigen technischen Gründen vereinfacht sich die Theorie in geeigneter Weise bei der Einstellung von DAGs anstelle von ungerichteten oder (zyklisch) gerichteten Graphen.

GMB
quelle

Sie können das Problem als LP schreiben, nicht wahr? Für zwei beliebige Eckpunkte u, v und einen beliebigen Pfad P von u nach v ist das Gewicht von P größer oder gleich dem Gewicht des angegebenen kürzesten Pfades zwischen u und v. Dies sind alles lineare Ungleichungen, und obwohl es solche gibt exponentiell viele, das Trennungsproblem ist in P (es ist nur ein Problem mit allen Paaren auf dem kürzesten Weg). Sie können ihn also mit dem Ellipsoid-Algorithmus lösen.

Mohammad
quelle