¿En qué clases de gráficos es NP-hard la ruta más corta limitada por recursos (RCSP)?

Estoy buscando vincular un problema en el que estoy trabajando con un problema NP-hard conocido. Creo que puedo modelar mi problema como un problema de ruta más corta con recursos limitados. Sin embargo, la estructura de mi gráfico no es completamente arbitraria. Por lo tanto, será útil saber cuándo RCSP se vuelve difícil. ¿Es difícil para un DAG, para un DAG plano, para un DAG con grado acotado? Cualquier ayuda sería muy apreciada!

cc.complexity-theory graph-algorithms np-hardness optimization nómada
fuente

¿Importa cuál es la restricción de recursos? por ejemplo, ¿tiene la forma de una restricción de "número de enlaces"?

Suresh Venkat

No sé si el recurso real es relevante para el resultado de la dureza. Sin embargo, la restricción de recursos es de la siguiente forma. Hay algún número (M) de conjuntos prohibidos, a los que puede pertenecer cada vértice. Las restricciones deben codificar que la ruta más corta satisfactoria no atraviesa todos los vértices en ninguno de estos conjuntos M (es decir, si el conjunto S prohibido contiene k vértices, la ruta más corta puede ser adyacente a hasta k-1 de ellos). Por lo tanto, cada enlace adyacente a un nodo restringido contiene la contribución de ese nodo a todos sus conjuntos prohibidos y buscamos un SP que respete estas restricciones.

nómada

Hojeando la literatura sobre el problema, he notado algunas cosas: 1) posibles nombres alternativos: ruta más corta restringida (CSP), enrutamiento de calidad de servicio (QoS) 2) el problema "estándar" utiliza un costo en cada borde, y un límite constante en la suma de los costos en el camino más corto 3) el problema es NP-completo en gráficos acíclicos

Daniel Apon

Este no es el camino más corto restringido. CSP tiene una solución de tiempo pseudo-polinomial.

Saeed

Respuestas:

No sé si todavía está interesado en esta (antigua) pregunta, y si entendí bien las limitaciones de recursos que dio en el comentario; sin embargo, parece que su problema (que es ligeramente diferente de los problemas habituales de RCSP) es NP-completo para gráficos planos (acíclicos dirigidos o no dirigidos) de grado máximo 3 .

$\varphi$ $n$ $x_1,...x_n$ $m$ $C_1,...C_m$

$M_k^+$ $x_k$ $\varphi$ $M_k^-$ $\bar{x}_k$ $\varphi$
$s$ $x_i$ $M_k^-$ $\bar{x}_k$ $M_k^+$ $x_k$
$C_j$ $C_j$ $M_k^+$ $M_k^-$
$t$

$s$ $t$ $\leq |V|$

$x_i$ $M_k^-$ $\bar{x}_i$ $M_k^+$ $x_i$ $M_k$

$M_k$

ingrese la descripción de la imagen aquí

$C_1 = x_1 \lor \bar{x}_2 \lor x_3$
$C_2 = x_2 \lor \bar{x}_3 \lor x_4$
$C_3 = \bar{x}_1 \lor x_3 \lor \bar{x}_2$

También puede hacer fácilmente el gráfico dirigido, acíclico y bipartito. Avíseme si necesita más detalles (o si entendí mal el problema :-).

$k$

Marzio De Biasi
fuente

k

$k$

@Saeed: correcto, editaré la pregunta. Uso yEd (aplicación de Java) ... no obtienes dibujos profesionales si los comparas con los producidos por tikz (usando TikZiT), pero puedes dibujar bocetos muy rápido (me tomó ~ 5 minutos para lo anterior).

Marzio De Biasi

Gracias;) Muchas veces necesito una herramienta para dibujar rápidamente, creo que esto está bastante bien.

Saeed