Prueba de que el problema de decisión de selección de ruta es NP-Completo

Prerrequisito: NP-Completitud
El problema de decisión del problema de selección de caminos pregunta si es posible seleccionar al menos k caminos de los caminos dados de un gráfico de modo que no haya dos caminos seleccionados que compartan ningún vértice.

Para probar que un problema es NP-Completo, necesitamos demostrar que es tanto NP como NP-Difícil. Usamos PSP para denotar nuestro problema de decisión de selección de ruta.

El PSP pertenece a NP:
Probamos esto construyendo un verificador de tiempo polinomial para el problema. Si algún problema está en NP, entonces, dado un ‘certificado’ (una solución) al problema y una instancia del problema (un gráfico G y un entero positivo k, en este caso), podremos verificar (comprobar si la solución dada es correcta o no) el certificado en tiempo polinomial.

El certificado para PSP es un conjunto de caminos P’. Estos son caminos independientes sin bordes comunes. Podemos verificar si hay k caminos que son independientes para el grafo dado G(V, E)) y caminos P de la siguiente manera:

Check if P' is a subset of P
If not, the given solution is wrong
The number of paths in P' is at least k
If not, the given solution is wrong

Initialize a list of boolean with length |V|
for each path p in P'
    for each vertex in p
        check if it is marked True in our list
        If so, the given solution is wrong
        Else, marks the vertex as True

Since no vertex was marked twice,
given solution is correct.

El verificador anterior es polytime ya que:

1. Se puede comprobar que P’ es un subconjunto de P en O(|P|).
2. La verificación del número de rutas en P’ se puede hacer en O(|P’|)
3. La comprobación de que todas las rutas son disjuntas se puede hacer en O(|V|)

Por lo tanto, complejidad de tiempo total:

por lo tanto, el PSP tiene verificabilidad de tiempo polinomial y, por lo tanto, pertenece a la clase NP.

El problema de decisión de la camarilla pertenece a NP-Hard:
para probar que PSP es NP Hard, tomamos un problema que ya se ha demostrado que es NP Hard (Conjunto independiente en nuestro caso), y mostramos que este problema se puede reducir a PSP. en tiempo polinomial. Como sabemos que el conjunto independiente es NP completo, también es NP duro.

Dada una instancia IS –

G=(V, E) and k 

Construimos la instancia de PSP de la siguiente manera:

Creamos un nuevo grafo G’. Para todo vértice v _i en G:

1. Denotamos un camino por P _i para v _i .
2. Sean e ₁ , e ₂ , …, e _r las aristas conectadas a v _i . Introducimos un vértice para cada una de esas aristas en G’. Además, introducimos un par de vértices en G’ – s _i , _ti .

De este modo,

Podemos ver claramente que la reducción anterior es politiempo (con complejidad = O (| V | + | E |)) ya que esencialmente estamos iterando sobre todos los vértices y los bordes en nuestro gráfico inicial.

Prueba:
prueba de que el problema de conjuntos independientes se reduce al problema de selección de caminos. Para probar que nuestra reducción es correcta probamos los siguientes dos argumentos.

(i) SÍ, instancia para IS => Sí, instancia para PSP
Tenemos, SÍ, instancia para IS.

1. Para un grafo G=(V, E) existe un conjunto independiente de tamaño al menos k.
2. Existen al menos k vértices que no comparten ninguna arista.
3. Existen al menos k caminos que no comparten ningún Node en la instancia de PSP. Dado que estamos definiendo los vértices de G para que sean análogos a los caminos en el caso de PSP y los bordes de G para que sean análogos a los vértices en esos caminos. Y cualquiera de estos Nodes de ruta compartida significaría que algunos dos vértices en el conjunto independiente comparten un borde común que nunca es posible.
4. Sí, instancia para PSP.

(ii) SÍ, instancia para PSP => Sí instancia para IS
ETP: No instancia para IS => No instancia para PSP. (Prueba por contrapositiva.).

Sabemos que siempre que exista un conjunto independiente de tamaño al menos k, existe un conjunto independiente de tamaño exactamente k (esto se puede hacer tomando el subconjunto de tamaño k del conjunto más grande). Por lo tanto, la contrapositiva también es verdadera. (es decir, siempre que no pueda existir un conjunto independiente de tamaño exactamente k, no puede existir un conjunto independiente de tamaño al menos k).

No tenemos ninguna instancia de IS.

1. Para un grafo G=(V, E) no puede existir un conjunto independiente de tamaño k.
2. No es posible encontrar k vértices de G que no compartan ninguna arista.
3. Todo conjunto S de vértices de tamaño k contendría vi y vj que comparten una arista.
4. Dado que estamos definiendo los vértices de G para que sean análogos a las rutas en la instancia de PSP y los bordes de G para que sean análogos a los vértices en esas rutas, cada conjunto de rutas de tamaño k en la instancia de PSP compartiría un Node.
5. No pueden existir k caminos que no compartan ningún Node en la instancia de PSP.
6. No hay instancia para PSP.

Por lo tanto, para un caso particular, el problema IS se reduce al PSP. Por lo tanto, PSP es NP-Hard.

Por lo tanto, el problema de decisión de selección de ruta es NP y NP-Hard. Por lo tanto, el problema de Decisión de Selección de Ruta es NP-Completo.