En informática y teoría de grafos , el problema del ciclo de peso cero es el problema de decidir si un grafo dirigido con pesos en los bordes (que pueden ser positivos, negativos o cero) tiene un ciclo en el que la suma de pesos es 0.
Un problema relacionado es decidir si el gráfico tiene un ciclo negativo, un ciclo en el que la suma de pesos es menor que 0. Este problema relacionado se puede resolver en tiempo polinomial utilizando el algoritmo de Bellman-Ford . Si no hay un ciclo negativo, entonces las distancias encontradas por el algoritmo de Bellman-Ford se pueden utilizar, como en el algoritmo de Johnson , para volver a ponderar los bordes del gráfico de tal manera que todos los pesos de los bordes se vuelvan no negativos y todas las longitudes de ciclo permanezcan sin cambios. Con esta reponderación, un ciclo de peso cero se vuelve trivial de detectar: existe si y solo si los bordes de peso cero no forman un gráfico acíclico dirigido . Por lo tanto, el caso especial del problema del ciclo de peso cero, en gráficos sin ciclo negativo, tiene un algoritmo de tiempo polinomial . [1]
En cambio, para los grafos que contienen ciclos negativos, detectar un ciclo simple de peso exactamente 0 es un problema NP-completo . [1] Esto es cierto incluso cuando los pesos son números enteros de magnitud polinómica. En particular, existe una reducción del problema de la trayectoria hamiltoniana , en un grafo no ponderado de vértices con vértices iniciales y finales especificados y , al problema del ciclo de peso cero en un grafo ponderado que se obtiene dando a todos los bordes de peso igual a uno, y agregando un borde adicional de a con peso . [2]
