Agregue una coincidencia a un camino hamiltoniano para reducir la distancia máxima entre pares de vértices dados

¿Cuál es la complejidad del siguiente problema?

Entrada :

• $H$ un camino hamiltoniano en $K_n$
• $R \subseteq [n]^2$ un subconjunto de pares de vértices
• un entero positivo $k$

Consulta : ¿hay una M coincidente tal que para cada ( v , u ) ∈ R , d G ( v , u ) ≤ k ? (donde G = ( [ n ] , M ∪ H ) )$M$$(v,u) \in R$$d_G(v,u) \leq k$
$G = ([n], M\cup H)$

He estado discutiendo con un amigo sobre este problema. Mi amigo piensa que el problema está en el tiempo polinómico. Creo que es NP-completo.

Esta respuesta es incorrecta .

Tu amigo tiene razón. Su problema (tal como lo interpreta Sasho) no impone ninguna restricción a la cardinalidad de la coincidente . Por lo tanto, elegir C ser un juego entre los pares en R . Entonces, para cualquier entero positivo k , la distancia entre cada par en R es menor que k .$C$$C$$R$$k$$R$$k$

Su problema se vuelve interesante si se fuerza caminos para tener bordes tanto de la coincidencia de y la trayectoria P .$C$$P$

ACTUALIZACIÓN: la respuesta a continuación no es correcta, porque supuse erróneamente que la ruta hamiltoniana está en un gráfico arbitrario, no en . Lo dejo sin borrar, tal vez pueda arreglarlo o dará algunas pistas para otra respuesta.$K_n$

Creo que es NP-completo. Esta es una idea de reducción muy informal / rápida de 3SAT

Para todas las variables añadir un "artilugio variable" con:$x_i$

• tres nodos $X_i, +X_i, -X_i$
• dos aristas variables y ( X i , - X i$(X_i,+X_i)$$(X_i,-X_i)$

Agregue un nodo de origen y conéctelo a todas las variables X i .$S$$X_i$

Para cada cláusula agregue un nodo C j y conéctelo a las variables correspondientes + X i o - X i que forman la cláusula.$C_j$$C_j$$+X_i$$-X_i$

La siguiente imagen representa: $(+x_1 \lor -x_2 \lor -x_3) \land (-x_2 \lor x_3 \lor x_4)$

El conjunto (nodos que deben ser vinculados) contiene ( S , C 1 ) , ( S , C 2 ) , . . $R$$(S, C_1), (S,C_2), ...$

La ruta simple debe incluir todos los bordes "AZUL" excepto los bordes variables ( X i , + X i ) y ( X i , - X i ) (en la imagen de arriba los bordes azules representan los bordes que incluimos en P ).$P$$(X_i, +X_i)$$(X_i, -X_i)$$P$

En este punto, la fórmula inicial es satisfactoria si y solo si la ruta más corta desde hasta cada nodo de la cláusula C j no es mayor que tres. De hecho, para alcanzar una cláusula desde S en tres pasos, debemos atravesar al menos una variable X i : S → X i → ± X i → C j . Por lo tanto, debemos atravesar uno de los dos bordes: X i → + X i o X i → - X i ) e incluirlo en $S$$C_j$$S$$X_i$$S \to X_i \to \pm X_i \to C_j$$X_i \to +X_i$$X_i \to -X_i)$$C$(porque por construcción no es parte de ). Pero no se pueden incluir ambos, porque comparten un vértice.$P$

Pero no estamos seguros de poder construir una ruta simple que incluya todos los bordes azules porque algunos nodos tienen más de un borde azul incidente.$P$

Para solucionar esto, reemplazamos cada nodo con múltiples bordes azules incidentes, con un árbol que contiene solo pares de bordes azules incidentes que se incluirán en y bordes que los separan y que deberían incluirse en C para llegar a los nodos de la cláusula:$P$$C$

El gráfico original se convierte en:

$K$$C_j$$S$

$C$

$P$