Проблема цикла с нулевым весом

В информатике и теории графов проблема цикла с нулевым весом — это проблема определения того, имеет ли ориентированный граф с весами на ребрах (которые могут быть положительными, отрицательными или нулевыми) цикл , в котором сумма весов равна 0.

Связанная проблема состоит в том, чтобы решить, имеет ли граф отрицательный цикл, цикл, в котором сумма весов меньше 0. Эту связанную проблему можно решить за полиномиальное время с использованием алгоритма Беллмана – Форда . Если отрицательного цикла нет, то расстояния, найденные алгоритмом Беллмана-Форда, можно использовать, как и в алгоритме Джонсона , для повторного взвешивания ребер графа таким образом, чтобы все веса ребер стали неотрицательными, а все длины циклов остались без изменений. При таком повторном взвешивании цикл с нулевым весом становится тривиальным для обнаружения: он существует тогда и только тогда, когда ребра с нулевым весом не образуют ориентированный ациклический граф . Следовательно, частный случай проблемы цикла с нулевым весом на графах без отрицательного цикла имеет алгоритм с полиномиальным временем .

Напротив, для графов, содержащих отрицательные циклы, обнаружение простого цикла с весом ровно 0 является NP-полной задачей. Это верно, даже если веса являются целыми числами полиномиальной величины. В частности, существует редукция гамильтоновой задачи о пути на $n$-вершинный невзвешенный граф $G$ с указанными начальной и конечной вершинами $s$ и $t$, к проблеме цикла с нулевым весом на взвешенном графе, полученном заданием всех ребер $G$ вес, равный единице, и добавление дополнительного ребра из $t$ к $s$ с весом $1-n$.