Árbol de expansión mínimo sobre todas las coincidencias de vértices

Me encontré con este problema de coincidencia para el que no puedo escribir un algoritmo de tiempo polinómico.

Supongamos que sean gráficos ponderados completos con conjuntos de vértices y , respectivamente, donde . Además, dejar que y ser las funciones de ponderación en los bordes de y , respectivamente. $P, Q$ $P_V$ $Q_V$ $|P_V| = |Q_V|=n$ $w_P$ $w_Q$ $P$ $Q$

Para una biyección modificamos de la siguiente manera: Si y con Luego establezca $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)$ . Denote esta gráfica modificada por y deje que sea la suma de los pesos del árbol de expansión mínimo de . $w_Q(q, q^\prime) = w_P(p, p^\prime)$ $Q_f$ $W(Q_f)$ $Q_f$

Problema: Minimizar sobre todas las biyecciones . $W(Q_f)$ $f: P_V \to Q_V$

¿Qué tan difícil es este problema? Si es "difícil": ¿qué pasa con los algoritmos de aproximación?

graph-theory optimization MEGABYTE
fuente

¿Podemos suponer que los pesos en P y Q satisfacen por separado la desigualdad del triángulo? Porque si es así, encontrar un MST en cada uno de ellos por separado, formando un recorrido de Euler para convertirlo en un camino de vendedor ambulante aproximado, y elegir una coincidencia que coincida con los vértices en las posiciones de camino correspondientes parece que debería ser una aproximación de 2 a su problema .

David Eppstein

@DavidEppstein: sí, los pesos satisfacen la desigualdad del triángulo. Tu idea parece interesante, ¡gracias!

Respuestas:

(Movido de los comentarios) Aquí hay una idea para obtener una aproximación de factor constante, suponiendo que P y Q satisfagan la desigualdad del triángulo. Pensé que podría dar una aproximación de 2, pero todo lo que puedo probar en este momento es una relación de aproximación de 4.

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

(2) En , encuentre un árbol de expansión mínimo y use la técnica de recorrido de Euler que dobla el camino para encontrar un camino con como máximo el doble del peso. Hacer lo mismo con independencia de . El resultado son dos árboles isomorfos (ambos caminos) que son por separado como máximo el doble del peso de los MST de su gráfico y, por lo tanto, como máximo el doble del costo de la solución para el problema del árbol de expansión isomorfo mínimo, y cuatro veces el peso del problema original . $P$ $Q$

(3) El problema original es NP-completo, por una reducción del camino hamiltoniano. Deje que se defina a partir de un gráfico en el que desea probar la existencia de un camino hamiltoniano; defina cuando es una arista en y cuando no es una arista. Deje que se defina exactamente de la misma manera a partir de un gráfico de ruta. Luego hay una solución del costo total si y solo si la gráfica a partir de la cual se definió tiene una ruta hamiltoniana. Probablemente esto también se pueda usar para probar la imposibilidad de aproximación por debajo de alguna constante fija. $P$ $P(pq)=1$ $pq$ $P$ $2$ $pq$ $Q$ $n-1$ $P$

David Eppstein
fuente

Gracias, esta es una excelente respuesta. (Aparentemente, no soy elegible para otorgarle la recompensa en las próximas 18 horas.)

¿Cómo sobre el uso del : Aproximación a la - Path TSP (tratar cada y ) para obtener los dos árboles (es decir, caminos)? arxiv.org/abs/1110.4604

(1 + \sqrt{5}) / 2

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

s

$s$

t

$t$

s

$s$

p

$p$

Magnus Lie Hetland el

Pensándolo bien, eso solo le daría una relación para la ruta óptima, por supuesto, no el MST. Entonces ... no importa;)

Magnus Lie Hetland