Minimalne drzewo opinające dla wszystkich dopasowań wierzchołków

Natknąłem się na ten problem z dopasowaniem, dla którego nie jestem w stanie zapisać algorytmu czasu wielomianowego.

Pozwolić $P, Q$ być kompletnymi wykresami ważonymi z zestawami wierzchołków odpowiednio i , gdzie . Ponadto pozwalają i być funkcje ciężar na krawędziach i , odpowiednio. $P_V$ $Q_V$ $|P_V| = |Q_V|=n$ $w_P$ $w_Q$ $P$ $Q$

W przypadku modyfikujemy w następujący sposób: Jeśli i z a następnie ustaw . Oznacz ten zmodyfikowany wykres przez i niech będzie sumą wag minimalnego drzewa . $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)$ $w_Q(q, q^\prime) = w_P(p, p^\prime)$ $Q_f$ $W(Q_f)$ $Q_f$

Problem: Zminimalizuj we wszystkich . $W(Q_f)$ $f: P_V \to Q_V$

Jak trudny jest ten problem? Jeśli „twardy”: co z algorytmami aproksymacyjnymi?

graph-theory optimization

— MB
źródło

Czy możemy założyć, że masy w P i Q oddzielnie spełniają nierówność trójkąta? Ponieważ jeśli tak, to znalezienie MST w każdym z nich osobno, utworzenie trasy Euler, aby przekształcić ją w przybliżoną ścieżkę podróżnego sprzedawcy i wybranie dopasowania, które pasuje do wierzchołków w odpowiednich pozycjach ścieżki, wygląda na to, że powinno to być przybliżenie 2 do twojego problemu .

— David Eppstein,

@DavidEppstein: tak, masy spełniają nierówność trójkąta. Twój pomysł wygląda interesująco, dziękuję!

— MB

(Przeniesiono z komentarzy) Oto pomysł uzyskania stałego przybliżenia współczynnika, zakładając, że P i Q spełniają nierówność trójkąta. Myślałem, że może to dać przybliżenie 2, ale wszystko, co mogę teraz udowodnić, to przybliżenie równe 4.

(1) W opisanym problemie waga krawędzi $pq$ na połączonym wykresie (po korespondencji $p$ - $p'$ i $q$ - $q'$ jest określony) jest $\max\{P(pq),Q(p'q')\}$ . Zamiast tego . Traci to co najwyżej współczynnik dwa, ale ułatwia opisanie problemu: próbujemy teraz znaleźć drzewo rozpinające w , a drzewo rozpinające izomorficzne w , o minimalnej masie całkowitej. Zależność między i wynika następnie z izomorfizmu między tymi dwoma drzewami. $P(pq)+Q(p'q')$ $P$ $Q$ $P$ $Q$

(2) W znajdź minimalne drzewo rozpinające i użyj techniki zwiedzania Eulera podwajającej ścieżkę, aby znaleźć ścieżkę o maksymalnej wadze dwa razy większej. Czy to samo niezależnie w . Rezultatem są dwa drzewa izomorficzne (obie ścieżki), które są oddzielnie co najwyżej dwa razy większe niż MST ich wykresu, a zatem co najwyżej dwa razy więcej niż koszt rozwiązania problemu minimalnego izomorficznego drzewa opinającego i czterokrotnie większy niż pierwotny problem . $P$ $Q$

(3) Pierwotny problem jest NP-zupełny, przez redukcję ze ścieżki hamiltonowskiej. Pozwól zdefiniować na podstawie wykresu, na którym chcesz przetestować istnienie ścieżki hamiltonowskiej; zdefiniuj gdy jest krawędzią w i gdy nie jest krawędzią. Niech będzie zdefiniowane dokładnie w ten sam sposób na podstawie wykresu ścieżki. Następnie istnieje rozwiązanie kosztu całkowitego wtedy i tylko wtedy, gdy wykres, na podstawie którego zdefiniowano ma ścieżkę hamiltonowską. Prawdopodobnie można to również wykorzystać do udowodnienia niedopuszczalności poniżej pewnej stałej stałej. $P$ $P(pq)=1$ $pq$ $P$ $2$ $pq$ $Q$ $n-1$ $P$

— David Eppstein
źródło

Dziękuję, to doskonała odpowiedź. (Najwyraźniej nie jestem uprawniony do przyznania nagrody w ciągu najbliższych 18 godzin.)

— MB 10.13

Jak o użyciu -approximation dla - Ścieżka TSP (spróbuj co i ), aby uzyskać dwa drzewa (czyli ścieżki)? arxiv.org/abs/1110.4604

(1 + \sqrt{5}) / 2

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

s

$s$

t

$t$

s

$s$

p

$p$

— Magnus Lie Hetland

Po zastanowieniu dałoby to tylko stosunek do optymalnej ścieżki, oczywiście, nie do MST. Więc… nieważne;)

— Magnus Lie Hetland