LISTA DE PROBLEMAS

En el campo matemático de la teoría de grafos, el problema del camino hamiltoniano y el problema del ciclo hamiltoniano son problemas para determinar si existe un camino hamiltoniano (un camino en un gráfico dirigido o no dirigido que visita cada vértice exactamente una vez) o un ciclo hamiltoniano en un gráfico dado ( ya sea dirigida o no dirigida ). Ambos problemas son NP completos . ^[1]

El problema del ciclo hamiltoniano es un caso especial del problema del vendedor ambulante , que se obtiene al establecer la distancia entre dos ciudades en una si son adyacentes y dos en caso contrario, y verificar que la distancia total recorrida sea igual a n (si es así, la ruta es un circuito hamiltoniano; si no hay un circuito hamiltoniano, la ruta más corta será más larga).

Reducción entre el problema de la ruta y el problema del ciclo [ editar ]

Hay una relación simple entre los problemas de encontrar un camino hamiltoniano y un ciclo hamiltoniano:

• En una dirección, el problema del camino hamiltoniano para el gráfico G es equivalente al problema del ciclo hamiltoniano en un gráfico H obtenido de G al agregar un nuevo vértice xy conectar x a todos los vértices de G. Por lo tanto, encontrar un camino hamiltoniano no puede ser significativamente más lento (en el peor de los casos, en función del número de vértices) que encontrar un ciclo hamiltoniano.
• En la otra dirección, el problema del ciclo hamiltoniano para un gráfico G es equivalente al problema del camino hamiltoniano en el gráfico H obtenido copiando un vértice v de G, v ', es decir, dejando que v' tenga la misma vecindad que v, y agregando dos vértices ficticios de grado uno y conectándolos con v y v ', respectivamente. ^[2]

Algoritmos [ editar ]

Hay n ! diferentes secuencias de vértices que podrían ser trayectorias hamiltonianas en un gráfico n- vértice dado (y están, en un gráfico completo ), por lo que un algoritmo de búsqueda de fuerza bruta que prueba todas las secuencias posibles sería muy lento. Un algoritmo exacto temprano para encontrar un ciclo hamiltoniano en un gráfico dirigido fue el algoritmo enumerativo de Martello. ^[3] Un procedimiento de búsqueda por Frank Rubin ^[4]divide los bordes del gráfico en tres clases: los que deben estar en la ruta, los que no pueden estar en la ruta y los indecisos. A medida que avanza la búsqueda, un conjunto de reglas de decisión clasifica los bordes indecisos y determina si detener o continuar la búsqueda. El algoritmo divide el gráfico en componentes que se pueden resolver por separado. Además, se puede utilizar un algoritmo de programación dinámica de Bellman, Held y Karp para resolver el problema en el tiempo O ( n ²  2 ⁿ ). En este método, se determina, para cada conjunto S de vértices y cada vértice v en S , si hay una ruta que cubra exactamente los vértices en S y termine en v. Para cada elección de S y v , existe una ruta para ( S , v ) si y solo si v tiene un vecino w tal que exista una ruta para ( S  -  v , w ), que puede buscarse a partir de información ya calculada en el programa dinámico ^[5] [6]

Andreas Björklund proporcionó un enfoque alternativo utilizando el principio de inclusión-exclusión para reducir el problema de contar el número de ciclos hamiltonianos a un problema de conteo más simple, de las cubiertas del ciclo de conteo, que se puede resolver calculando ciertos determinantes de la matriz. Usando este método, mostró cómo resolver el problema del ciclo de Hamilton en gráficos arbitrarios de n -vértices mediante un algoritmo de Monte Carlo en el tiempo O (1.657 ⁿ ); para gráficos bipartitos, este algoritmo se puede mejorar aún más al tiempo o (1.415 ⁿ ). ^[7]

Para gráficos de grado máximo tres, una búsqueda cuidadosa de retroceso puede encontrar un ciclo hamiltoniano (si existe) en el tiempo O (1.251 ⁿ ). ^[8]

Los caminos y ciclos hamiltonianos se pueden encontrar utilizando un solucionador SAT .

Debido a la dificultad de resolver los problemas del camino y el ciclo de Hamilton en las computadoras convencionales, también se han estudiado en modelos de computación no convencionales. Por ejemplo, Leonard Adleman demostró que el problema del camino hamiltoniano puede resolverse usando una computadora de ADN . Explotando el paralelismo inherente a las reacciones químicas, el problema puede resolverse utilizando una serie de pasos de reacción química lineales en el número de vértices del gráfico; sin embargo, requiere un número factorial de moléculas de ADN para participar en la reacción. ^[9]

También se ha propuesto una solución óptica al problema hamiltoniano. ^[10] La idea es crear una estructura tipo gráfico hecha de cables ópticos y divisores de haz que sean atravesados ​​por la luz para construir una solución al problema. El punto débil de este enfoque es la cantidad de energía requerida que es exponencial en el número de nodos.

Complejidad [ editar ]

El problema de encontrar un ciclo o camino hamiltoniano está en FNP ; El problema de decisión análoga es probar si existe un ciclo o camino hamiltoniano. Los problemas del ciclo hamiltoniano dirigidos y no dirigidos fueron dos de los 21 problemas de NP completos de Karp . Permanecen NP completos incluso para tipos especiales de gráficos, como:

• gráficos bipartitos , ^[11]
• gráficos planos no dirigidos de grado máximo tres, ^[12]
• gráficos planos dirigidos con grado de entrada y salida a lo sumo dos, ^[13]
• 3 planos bipartitos regulares sin puente no direccionados ,
• Gráficos bipartitos 3-regulares 3 conectados, ^[14]
• subgrafías del gráfico de cuadrícula cuadrada , ^[15]
• subgrafías cúbicas del gráfico de cuadrícula cuadrada. ^[dieciséis]

Sin embargo, para algunas clases especiales de gráficos, el problema se puede resolver en tiempo polinómico:

• Los gráficos planos conectados a 4 son siempre hamiltonianos por un resultado debido a Tutte, y la tarea computacional de encontrar un ciclo hamiltoniano en estos gráficos puede llevarse a cabo en tiempo lineal ^[17] calculando una llamada ruta de Tutte .
• Tutte demostró este resultado al mostrar que cada gráfico plano 2-conectado contiene una ruta Tutte . Las rutas de Tutte a su vez pueden calcularse en tiempo cuadrático incluso para gráficos planos conectados a 2 ^[18] , que pueden usarse para encontrar ciclos hamiltonianos y ciclos largos en generalizaciones de gráficos planos.

Al poner todas estas condiciones juntas, queda abierto si los gráficos planos bipartitos tripartitos 3 conectados entre sí siempre deben contener un ciclo hamiltoniano, en cuyo caso el problema restringido a esos gráficos no podría ser NP completo; ver la conjetura de Barnette .

En los gráficos en los que todos los vértices tienen un grado impar, un argumento relacionado con el lema del apretón de manos muestra que el número de ciclos hamiltonianos a través de cualquier borde fijo siempre es par, por lo que si se da un ciclo hamiltoniano, también debe existir un segundo. ^[19] Sin embargo, encontrar este segundo ciclo no parece ser una tarea computacional fácil. Papadimitriou definió la clase de complejidad PPA para encapsular problemas como este.

En la teoría de grafos y la informática teórica , el problema del camino más largo es el problema de encontrar un camino simple de longitud máxima en un gráfico dado. Una ruta se llama simple si no tiene vértices repetidos; la longitud de una ruta puede medirse por su número de aristas o (en gráficos ponderados ) por la suma de los pesos de sus aristas. En contraste con el problema de la ruta más corta , que puede resolverse en tiempo polinómico en gráficos sin ciclos de peso negativo, el problema de la ruta más larga es NP-hard y la versión de decisión del problema, que pregunta si existe una ruta de al menos algunos longitud, es NP-completo. Esto significa que el problema de decisión no se puede resolver en tiempo polinómico para gráficos arbitrarios a menos que  P = NP . También se conocen resultados de dureza más fuertes que muestran que es difícil aproximarse . Sin embargo, tiene una solución de tiempo lineal para gráficos acíclicos dirigidos , que tiene aplicaciones importantes para encontrar la ruta crítica en los problemas de programación.

NP-dureza [ editar ]

La dureza NP del problema del camino más largo no ponderado se puede mostrar utilizando una reducción del problema del camino hamiltoniano : un gráfico G tiene un camino hamiltoniano si y solo si su camino más largo tiene una longitud n  - 1, donde n es el número de vértices en G . Debido a que el problema de la ruta de Hamilton es NP-completo, esta reducción muestra que la versión de decisión del problema de ruta más larga también es NP-completa. En este problema de decisión, la entrada es un gráfico G y un número k ; la salida deseada es "sí" si G contiene una ruta de k o más bordes, y no de lo contrario. ^[1]

Si el problema del camino más largo pudiera resolverse en tiempo polinómico, podría usarse para resolver este problema de decisión, encontrando un camino más largo y luego comparando su longitud con el número  k . Por lo tanto, el problema del camino más largo es NP-hard. La pregunta "¿existe una ruta simple en un gráfico dado con al menos k aristas" es NP-complete. ^[2]

En los gráficos completos ponderados con pesos de borde no negativos, el problema de la ruta más larga ponderada es el mismo que el problema de la ruta del vendedor viajero , porque la ruta más larga siempre incluye todos los vértices. ^[3]

Gráficos acíclicos y caminos críticos [ editar ]

Un camino más largo entre dos vértices dados s y t en un gráfico ponderado G es la misma cosa que un camino más corto en un gráfico - G deriva de G cambiando cada peso a su negación. Por lo tanto, si los caminos más cortos se pueden encontrar en - G , entonces los caminos más largos también pueden ser encontrados en G . ^[4]

Para la mayoría de los gráficos, esta transformación no es útil, ya que crea ciclos de longitud negativa en - G . Pero si G es un gráfico acíclico dirigido , entonces no se pueden crear ciclos negativos, y se puede encontrar una ruta más larga en G en tiempo lineal mediante la aplicación de un algoritmo de tiempo lineal para rutas más cortas en - G , que también es un gráfico acíclico dirigido. ^[4] Por ejemplo, para cada vértice v en un DAG dado, la longitud de la ruta más larga que termina en v se puede obtener mediante los siguientes pasos:

1. Encuentre un orden topológico del DAG dado.
2. Para cada vértice v del DAG, en el orden topológico, calcule la longitud de la ruta más larga que termina en v mirando a sus vecinos entrantes y agregando uno a la longitud máxima registrada para esos vecinos. Si v no tiene vecinos entrantes, establezca la longitud de la ruta más larga que termina en v en cero. En cualquier caso, registre este número para que los pasos posteriores del algoritmo puedan acceder a él.

Una vez hecho esto, se puede obtener el camino más largo en todo el DAG comenzando en el vértice v con el mayor valor registrado, luego retrocediendo repetidamente hacia su vecino entrante con el mayor valor registrado e invirtiendo la secuencia de vértices encontrados en de esta manera.

El método de ruta crítica para programar un conjunto de actividades implica la construcción de un gráfico acíclico dirigido en el que los vértices representan hitos del proyecto y los bordes representan actividades que deben realizarse después de un hito y antes de otro; cada ventaja se pondera con una estimación de la cantidad de tiempo que llevará completar la actividad correspondiente. En dicho gráfico, la ruta más larga desde el primer hito hasta el último es la ruta crítica, que describe el tiempo total para completar el proyecto. ^[4]

Las rutas más largas de los gráficos acíclicos dirigidos también se pueden aplicar en el dibujo de gráficos por capas : la asignación de cada vértice v de un gráfico acíclico dirigido G a la capa cuyo número es la longitud de la ruta más larga que termina en v da como resultado una asignación de capa para G con el mínimo posible número de capas ^[5]

Aproximación [ editar ]

Björklund, Husfeldt y Khanna (2004) escriben que el problema del camino más largo en los gráficos no ponderados no dirigidos "es notorio por la dificultad de comprender su dureza de aproximación". ^[6] El mejor algoritmo de aproximación de tiempo polinómico conocido para este caso logra solo una relación de aproximación muy débil,$${\ displaystyle n / \ exp (\ Omega ({\ sqrt {\ log n}}))}. ^[7] Para todos{\ displaystyle \ epsilon> 0}, no es posible aproximar el camino más largo dentro de un factor de$${\ displaystyle 2 ^ {(\ log n) ^ {1- \ epsilon}}}a menos que NP esté contenido dentro del tiempo determinista cuasi-polinomial ; sin embargo, existe una gran brecha entre este resultado de aproximación y los algoritmos de aproximación conocidos para este problema. ^[8]

En el caso de gráficos no ponderados pero dirigidos, se conocen fuertes resultados de inaplicabilidad. Para cada{\ displaystyle \ epsilon> 0} el problema no puede ser aproximado dentro de un factor de $${\ displaystyle n ^ {1- \ epsilon}} a menos que P = NP, y con supuestos teóricos de complejidad más fuertes, no puede aproximarse a un factor de $${\ displaystyle n / \ log ^ {2+ \ epsilon} n}. ^[6] La técnica de codificación de colores se puede utilizar para encontrar rutas de longitud logarítmica, si existen, pero esto da una relación de aproximación de solo$${\ displaystyle O (n / \ log n)}. ^[9]

Complejidad parametrizada [ editar ]

El problema de la ruta más larga es el parámetro fijo manejable cuando se parametriza por la longitud de la ruta. Por ejemplo, se puede resolver en tiempo lineal en el tamaño del gráfico de entrada (pero exponencial en la longitud de la ruta), mediante un algoritmo que realiza los siguientes pasos:

1. Realice una búsqueda en profundidad del gráfico. Dejar$${\ displaystyle d}ser la profundidad del árbol de búsqueda de profundidad primero resultante .
2. Use la secuencia de rutas de raíz a hoja del árbol de búsqueda de profundidad primero, en el orden en que fueron atravesadas por la búsqueda, para construir una descomposición de ruta del gráfico, con ancho de ruta$${\ displaystyle d}.
3. Aplique programación dinámica a esta descomposición de ruta para encontrar una ruta más larga en el tiempo$${\ displaystyle O (d! 2 ^ {d} n)}, dónde $${\ displaystyle n} es el número de vértices en el gráfico.

Dado que la ruta de salida tiene una longitud al menos tan grande como $${\ displaystyle d}, el tiempo de ejecución también está limitado por $${\ displaystyle O (\ ell! 2 ^ {\ ell} n)}, dónde $${\ displaystyle \ ell}es la longitud del camino más largo. ^[10] Utilizando la codificación por colores, la dependencia de la longitud del camino se puede reducir a exponencialmente individual. ^{[9] [11] [12] [13]} Una técnica de programación dinámica similar muestra que el problema de la ruta más larga también es manejable con parámetros fijos cuando se parametriza por el ancho del árbol del gráfico.

Para gráficos de ancho de camarilla acotado , el camino más largo también puede resolverse mediante un algoritmo de programación dinámica de tiempo polinómico. Sin embargo, el exponente del polinomio depende del ancho de la camarilla del gráfico, por lo que este algoritmo no es manejable con parámetros fijos. El problema de ruta más largo, parametrizado por ancho de camarilla, es difícil para la clase de complejidad parametrizada$${\ displaystyle W [1]}, mostrando que es poco probable que exista un algoritmo manejable de parámetro fijo. ^[14]

Clases especiales de gráficos [ editar ]

Dijkstra propuso un algoritmo de tiempo lineal para encontrar una ruta más larga en un árbol en la década de 1960, mientras que en 2002 se publicó una prueba formal de este algoritmo. ^[15] Además, se puede calcular una ruta más larga en tiempo polinómico en árboles ponderados, en gráficos de bloques , en cactus , ^[16] en gráficos de permutación bipartitos , ^[17] y en gráficos ptolemaicos . ^[18]

Para la clase de gráficos de intervalo , un$${\ displaystyle O (n ^ {4})}Se conoce el algoritmo de tiempo, que utiliza un enfoque de programación dinámica. ^[19] Este enfoque de programación dinámica ha sido explotado para obtener algoritmos de tiempo polinómico en las clases más grandes de gráficos de arco circular ^[20] y de gráficos de co-comparabilidad (es decir, de los complementos de gráficos de comparabilidad , que también contienen gráficos de permutación ), ^[21] ambos tienen el mismo tiempo de ejecución$${\ displaystyle O (n ^ {4})}. El último algoritmo se basa en las propiedades especiales del ordenamiento de vértices Lexicographic Depth First Search (LDFS) ^[22] de los gráficos de co-comparabilidad. Para los gráficos de co-comparabilidad también un algoritmo de tiempo polinomial alternativo con mayor tiempo de ejecución$${\ displaystyle O (n ^ {7})}se conoce, que se basa en el diagrama de Hasse del conjunto parcialmente ordenado definido por el complemento del gráfico de comparabilidad de entrada. ^[23]

Además, el problema de la ruta más larga se puede resolver en tiempo polinómico en cualquier clase de gráficos con ancho de árbol acotado o ancho de camarilla acotado, como los gráficos hereditarios de distancia . Finalmente, es claramente NP-hard en todas las clases de gráficos en las que el problema de la ruta de Hamilton es NP-hard, como en gráficos divididos , gráficos circulares y gráficos planos .