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?

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