Минимальное остовное дерево для всех совпадений вершин

Я столкнулся с этой проблемой соответствия, для которой я не могу записать алгоритм полиномиального времени.

Пусть - полные взвешенные графы с множествами вершин и соответственно, где . Кроме того, пусть и - весовые функции на ребрах и соответственно.$P, Q$$P_V$$Q_V$$|P_V| = |Q_V|=n$$w_P$$w_Q$$P$$Q$

Для биекции мы модифицируем следующим образом: если и с тогда установите . Обозначим этот модифицированный граф через и пусть будет суммой весов минимального остовного дерева .$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$

Проблема: Минимизируйте по всем биекциям .$W(Q_f)$$f: P_V \to Q_V$

Насколько сложна эта проблема? Если «сложно»: как насчет алгоритмов аппроксимации?

(Перемещено из комментариев) Вот идея получения приближения с постоянным множителем, если предположить, что P и Q удовлетворяют неравенству треугольника. Я думал, что это может дать 2-аппроксимацию, но все, что я могу доказать прямо сейчас, это коэффициент аппроксимации 4.

(1) В указанной задаче вес ребра в комбинированном графе (после определения соответствия - и - ) равен . Вместо этого давайте использовать . Это приводит к потере не более чем в два раза, но облегчает описание проблемы: теперь мы пытаемся найти остовное дерево в и изоморфное остовное дерево в с минимальным общим весом. Соответствие между и тогда дается изоморфизмом между этими двумя деревьями.$pq$$p$$p'$$q$$q'$$\max\{P(pq),Q(p'q')\}$$P(pq)+Q(p'q')$$P$$Q$$P$$Q$

(2) В найдите минимальное остовное дерево и используйте технику обхода Эйлера с удвоением пути, чтобы найти путь с максимальным удвоенным весом. Сделайте то же самое самостоятельно в . Результатом являются два изоморфных дерева (оба пути), которые по отдельности не более чем вдвое превышают вес MST их графа, и, следовательно, не более чем вдвое дороже решения минимальной изоморфной задачи на остовном дереве, и в четыре раза превышают вес исходной задачи. ,$P$$Q$

(3) Исходная задача является NP-полной, путем сокращения от гамильтонова пути. Пусть определено из графа, в котором вы хотите проверить существование гамильтонова пути; определите когда является ребром в и когда не является ребром. Пусть определен точно так же из графа путей. Тогда существует решение полной стоимости тогда и только тогда, когда граф, из которого была определена имеет гамильтонов путь. Вероятно, это также может быть использовано для доказательства неприемлемости ниже некоторой фиксированной константы.$P$$P(pq)=1$$pq$$P$$2$$pq$$Q$$n-1$$P$