Minimaler Spanning Tree über alle Vertex-Übereinstimmungen

9

Ich bin auf dieses Übereinstimmungsproblem gestoßen, für das ich keinen Polynomzeitalgorithmus aufschreiben kann.

Sei vollständig gewichtete Graphen mit Scheitelpunktsätzen P V bzw. Q V , wobei | P V | = | Q V | = n . Auch lassen w P und w Q sind die Gewichtsfunktionen an den Kanten von P und Q sind.P,QPVQV|PV|=|QV|=nwPwQPQ

Für eine Bijektion modifizieren wir Q folgendermaßen: Wenn f ( p ) = q und f ( p ' ) = q ' mit w P ( p , p ' ) > w Q ( q , q ' ) Dann setze w Q ( q , q ' ) = w P.f:PVQVQf(p)=qf(p)=qwP(p,p)>wQ(q,q) . Bezeichne diesen modifizierten Graphen mit Q f und sei W ( Q f ) die Summe der Gewichte des minimalen Spannbaums von Q f .wQ(q,q)=wP(p,p)QfW(Qf)Qf

Problem: Minimieren über alle Bijektionen F : P VQ V .W(Qf)f:PVQV

Wie schwer ist dieses Problem? Wenn "schwer": Was ist mit Approximationsalgorithmen?

MB
quelle
Können wir annehmen, dass die Gewichte in P und Q getrennt die Dreiecksungleichung erfüllen? Denn wenn ja, dann sollte es eine 2-Annäherung an Ihr Problem sein, eine MST in jeder von ihnen separat zu finden, eine Euler-Tour zu erstellen, um sie in einen ungefähren Pfad für reisende Verkäufer umzuwandeln, und eine Übereinstimmung zu wählen, die den Scheitelpunkten an den entsprechenden Pfadpositionen entspricht .
David Eppstein
@ DavidEppstein: Ja, die Gewichte erfüllen die Dreiecksungleichung. Ihre Idee sieht interessant aus, danke!
MB

Antworten:

11

(Aus den Kommentaren entfernt) Hier ist eine Idee, um eine konstante Faktornäherung zu erhalten, vorausgesetzt, P und Q erfüllen die Dreiecksungleichung. Ich dachte, es könnte eine 2-Näherung geben, aber alles, was ich jetzt beweisen kann, ist ein Näherungsverhältnis von 4.

pqppqqmax{P(pq),Q(pq)}P(pq)+Q(pq)PQPQ

(2) Suchen Sie in einen minimalen Spannbaum und verwenden Sie die Euler-Tour-Technik zur Pfadverdopplung, um einen Pfad mit höchstens dem doppelten Gewicht zu finden. Machen Sie dasselbe unabhängig in . Das Ergebnis sind zwei isomorphe Bäume (beide Pfade), die getrennt höchstens das Doppelte des Gewichts der MSTs ihres Graphen und damit höchstens das Doppelte der Kosten für die Lösung des minimalen isomorphen Spanning Tree-Problems und das Vierfache des Gewichts des ursprünglichen Problems betragen .PQ

(3) Das ursprüngliche Problem ist NP-vollständig durch eine Reduktion vom Hamilton-Pfad. Sei aus einem Graphen definiert, in dem Sie die Existenz eines Hamilton-Pfades testen möchten; definiere wenn eine Kante in und wenn keine Kante ist. Lassen auf genau die gleiche Art und Weise von einem Pfad Diagramm definiert werden. Dann gibt es eine Lösung der Gesamtkosten genau dann, wenn der Graph, aus dem definiert wurde, einen Hamilton-Pfad hat. Wahrscheinlich kann dies auch verwendet werden, um eine Unannäherbarkeit unterhalb einer festen Konstante zu beweisen.PP(pq)=1pqP2pqQn1P

David Eppstein
quelle
Vielen Dank, dies ist eine hervorragende Antwort. (Anscheinend bin ich nicht berechtigt, Ihnen das Kopfgeld in den nächsten 18 Stunden
MB
Wie wäre es mit der -Anpassung für die - Pfad TSP (versuchen alle und ) die beiden Bäume zu erhalten (dh Pfade)? arxiv.org/abs/1110.4604(1+5)/2stsp
Magnus Lie Hetland
Beim zweiten Gedanken würde Ihnen das natürlich nur ein Verhältnis für den optimalen Pfad geben, nicht für den MST. Also ... vergiss es nicht;)
Magnus Lie Hetland