Arbre couvrant minimum sur toutes les correspondances de sommets

J'ai rencontré ce problème d'appariement pour lequel je ne suis pas en mesure d'écrire un algorithme de temps polynomial.

Soit graphiques pondérés complets avec les ensembles de sommets et , respectivement, où . Soit également et les fonctions de pondération sur les bords de et , respectivement.P V Q V | P V | = | Q V | = n w P w Q P $P, Q$$P_V$$Q_V$$|P_V| = |Q_V|=n$$w_P$$w_Q$$P$$Q$

Pour une bijection nous modifions de la manière suivante: Si et avec puis définissez . Notons ce graphique modifié par et soit la somme des poids de l'arbre couvrant minimum de . Q f ( p ) = q f ( p ′ ) = q ′ w P ( p , p ′ ) > w Q ( q , q ′ ) w Q ( q , q ′ ) = w P ( p , p ′ ) Q f W ( $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$Q $W(Q_f)$$Q_f$

Problème: Minimisez sur toutes les bijections .f : P V → Q $W(Q_f)$$f: P_V \to Q_V$

Quelle est la difficulté de ce problème? Si "dur": qu'en est-il des algorithmes d'approximation?

(Déplacé des commentaires) Voici une idée pour obtenir une approximation constante des facteurs, en supposant que P et Q satisfont l'inégalité du triangle. Je pensais que cela pourrait donner une approximation de 2, mais tout ce que je peux prouver en ce moment est un rapport d'approximation de 4.

(1) Dans le problème indiqué, le poids du bord dans le graphique combiné (après que la correspondance - et - est déterminée) est . À la place, utilisons . Cela perd au plus un facteur deux mais rend le problème plus facile à décrire: nous essayons maintenant de trouver un arbre couvrant en , et un arbre couvrant isomorphe en , avec un poids total minimum. La correspondance entre et est alors donnée par l'isomorphisme entre ces deux arbres.p p ′ q q ′ max { P ( p q ) , Q ( p ′ q ′ ) } P ( p q ) + Q ( p ′ q ′ ) P Q P $pq$$p$$p'$$q$$q'$$\max\{P(pq),Q(p'q')\}$$P(pq)+Q(p'q')$$P$$Q$$P$$Q$

(2) Dans , trouvez un arbre couvrant minimum et utilisez la technique de tour Euler doublant le chemin pour trouver un chemin avec au plus le double du poids. Faites la même chose indépendamment dans . Le résultat est deux arbres isomorphes (les deux chemins) qui sont séparément au plus deux fois le poids des MST de leur graphique, et donc au plus deux fois le coût de la solution au problème de l'arbre couvrant isomorphe minimum, et quatre fois le poids du problème d'origine .$P$$Q$

(3) Le problème d'origine est NP-complet, par une réduction du chemin hamiltonien. Soit défini à partir d'un graphe dans lequel vous souhaitez tester l'existence d'un chemin hamiltonien; définir lorsque est un bord dans et lorsque n'est pas un bord. Soit défini exactement de la même manière à partir d'un graphe de chemin. Il existe alors une solution du coût total si et seulement si le graphe à partir duquel été défini a un chemin hamiltonien. Cela peut également être utilisé pour prouver l'inapproximabilité en dessous d'une constante fixe.P ( p q ) = 1 p q P 2 p q Q n - 1 $P$$P(pq)=1$$pq$$P$$2$$pq$$Q$$n-1$$P$