¿Cómo probar la búsqueda de dos caminos que son al menos k los bordes, aparte es NP-HARD?

Question

Let $ g= (v, e) $ Sé un gráfico sin peso, no dirigido y conectado. Dados dos vértices de inicio $ s_1 $ y $ s_2 $ y dos vértices finales $ T_1 $ y $ t_2 $ Hay una ruta de $ s_1 $ a $ t_1 $ y $ s_2 $ a $ t_2 $ de modo que el número más cercano de bordes entre las dos rutas es al menos $ k $ ? Dos rutas son $ k $ Cerrar si el mínimo de las distancias más cortas entre cualquier vértice en la primera ruta a cualquier vértice en la segunda ruta es $ k $ .

Estaba pensando en reducirla de 3SAT y dejar que el primer camino representa las variables y el segundo camino representan las cláusulas, pero no estoy seguro de dónde ir allí.

Answer 1

Puede reducir de 3SAT.

El gráfico tiene dos partes. Una parte es la parte "variable". Para cada una de las variables $ v_1, \ ldots, v_n $ Hay dos tres vértices $ v_i ^ +, v_i ^ - , v_i $ , y esta parte consta de los siguientes bordes, para $ i \ in [n] $ :

$$ (v_ {i-1}, v_i ^ +), (v_ {I-1}, V_I ^ -), (V_I ^ +, V_I), ( v_i ^ -, v_i) $$

aquí $ v_0 $ es un nuevo vértice, identificado con $ s_1 $ y $ v_n $ se identifica con $ t_1 $ .

La segunda parte es la parte "cláusula". Para cada una de las cláusulas $ c_1, \ ldots, c_m $ allí cuatro vértices $ w_j ^ 1, w_j ^ 2, w_j ^ 3, W_J $ , conectado mucho como antes, con $ s_2 $ y $ t_2 $ .

Nos conectamos $ v_i ^ b $ con $ w_j ^ r $ a través de un camino de longitud < Span Class="Math-contenedor"> $ K $ (para un poco de constante constante $ k $ ) si el literal $ v_i ^ b $ (ya sea $ v_i $ o $ \ overline {v_i} $ < / SPAN>, de acuerdo con $ b $ ) es el opuesto de $ j $ 'th literal en $ c_j $ .

Además, tomamos todos los puntos finos de estos caminos y conectamos todos ellos (convirtiéndolos en una camarilla).

Podemos pensar en un $ (s_1, t_1) $ -path como una tarea de verdad, y de un $ (S_2, T_2) $ -path como identificando un literal satisfecho en cada cláusula. La distancia mínima es más de $ k $ si este es el caso, y solo $ k $ de otra manera .

También debe verificar que no hay un punto para que los caminos se crucen entre las partes. Si solo se cruza una de las rutas, las dos rutas se cerrarán juntas (a una distancia constante, lo que para un $ k $ será más pequeño que $ K $ ) inmediatamente después del cruce. Si ambos cruzan, entonces la campaña de punto medio se asegurará de que estén a la distancia a lo sumo 1.