Minimaler Spanning Tree über alle Vertex-Übereinstimmungen

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

Sei vollständig gewichtete Graphen mit Scheitelpunktsätzen bzw. , wobei . Auch lassen und sind die Gewichtsfunktionen an den Kanten von und sind. $P, Q$ $P_V$ $Q_V$ $|P_V| = |Q_V|=n$ $w_P$ $w_Q$ $P$ $Q$

Für eine Bijektion modifizieren wir folgendermaßen: Wenn und mit Dann setze $f: P_V \to Q_V$ $Q$ $f(p) = q$ $f(p^\prime) = q^\prime$ $w_P(p, p^\prime) > w_Q(q, q^\prime)$ . Bezeichne diesen modifizierten Graphen mit und sei die Summe der Gewichte des minimalen Spannbaums von . $w_Q(q, q^\prime) = w_P(p, p^\prime)$ $Q_f$ $W(Q_f)$ $Q_f$

Problem: Minimieren über alle Bijektionen . $W(Q_f)$ $f: P_V \to Q_V$

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

graph-theory optimization 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!

Antworten:

(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.

$pq$ $p$ $p'$ $q$ $q'$ $\max\{P(pq),Q(p'q')\}$ $P(pq)+Q(p'q')$ $P$ $Q$ $P$ $Q$

(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 . $P$ $Q$

(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. $P$ $P(pq)=1$ $pq$ $P$ $2$ $pq$ $Q$ $n-1$ $P$

David Eppstein
quelle

Vielen Dank, dies ist eine hervorragende Antwort. (Anscheinend bin ich nicht berechtigt, Ihnen das Kopfgeld in den nächsten 18 Stunden

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 + \sqrt{5}) / 2

$(1+\sqrt{5})/2$

s

$s$

t

$t$

s

$s$

p

$p$

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