Найти отрицательный цикл с ограничениями вершин

Для данного графа со взвешенными ребрами, как мы можем найти отрицательный цикл, который содержит хотя бы одну вершину в данном наборе вершин ? Спасибо.$\{V_1, V_2, \ldots, V_k\}$

Если вам не требуется, чтобы цикл был простым, то разбейте (направленный) граф на его сильно связанные компоненты, и для каждого компонента, содержащего одну из заданных вершин , проверьте, содержит ли компонент отрицательный цикл. Если нет компонента, нет отрицательного цикла, содержащего какой-либо V i . Но если какой-то компонент делает это, вы можете найти (непростой) отрицательный цикл, содержащий V i , взяв множество копий отрицательного цикла и добавив к нему пути к некоторой вершине в цикле и к нему из V i . (Общее время нахождения неявного представления желаемого цикла будет таким же, как время нахождения отрицательного цикла в ориентированном графе, например, O $V_i$$V_i$$V_i$$V_i$ , если я помню.)$O(nm)$

Если вам требуется, чтобы цикл был простым, то задача становится NP-полной, даже если задана только одна вершина . (Вы можете свести гамильтонов путь к задаче: чтобы найти гамильтонов путь от заданного источника S к заданному стоку T в данном графе G , укажите вес существующих ребер -1, затем добавьте искусственную вершину V 1 с двумя ребрами стоимость N / 2 - 0,01 каждая, одна от V 1 до S и одна от T до V 1. )$V_1$$S$$T$$G$$V_1$$N/2-0.01$$V_1$$S$$T$$V_1$

Если вы позволите циклу повторять вершины, но не ребра, я полагаю, что он все еще является NP-полным (аналогичным сокращением, но разбивая каждую вершину на направленное ребро ( v , v ′ ) стандартным способом).$v$$(v,v')$

Я собираюсь предположить, что ваши входные данные являются ориентированным графом; Я не знаю, как это сделать для неориентированного дела.

Сделайте копий набора вершин вашего графа, где n - количество вершин в графе. Замените каждое ребро от u до v в вашем исходном графе ребрами, которые идут от копии i из u до копии i + 1 из v для всех вариантов i . Кроме того, если u принадлежит указанному набору вершин, но не иначе, также включите ребро, которое идет от копии i из u к копии 0 из v .$n$$n$$u$$v$$i$$u$$i+1$$v$$i$$u$$i$$u$$0$$v$

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