Znajdź cykl ujemny z ograniczeniami wierzchołków

W przypadku wykresu z ważonymi krawędziami, jak możemy znaleźć cykl ujemny, który zawiera co najmniej jeden wierzchołek w danym zestawie wierzchołków ? Dzięki.$\{V_1, V_2, \ldots, V_k\}$

Jeśli nie chcesz, aby cykl był prosty, podziel wykres (skierowany) na jego silnie połączone komponenty i dla każdego komponentu zawierającego jeden z podanych wierzchołków sprawdź, czy komponent zawiera cykl ujemny. Jeśli żaden składnik tego nie robi, nie ma cyklu ujemnego zawierającego jakiekolwiek V i . Ale jeśli ma to jakiś składnik, można znaleźć (nie prosty) cykl ujemny zawierający V i , pobierając wiele kopii cyklu ujemnego i dodając do tych ścieżek do i od pewnego wierzchołka cyklu do V i . (Całkowity czas znalezienia niejawnej reprezentacji pożądanego cyklu będzie taki sam jak czas znalezienia ujemnego cyklu na ukierunkowanym wykresie, np. O $V_i$$V_i$$V_i$$V_i$ , jeśli pamiętam.)$O(nm)$

Jeśli nie wymagają cykl się prosta, to problem staje NP-zupełny, nawet jeśli tylko jeden wierzchołek jest podane. (Możesz zredukować ścieżkę hamiltonianu do problemu: aby znaleźć ścieżkę hamiltonianu z danego źródła S do danego ujścia T na danym wykresie G , nadaj istniejącej krawędzi wagę -1, a następnie dodaj sztuczny wierzchołek V 1 z dwiema krawędziami koszt N / 2 - 0,01 każdy, jeden od V 1 do S, a drugi od T do V 1 ).$V_1$$S$$T$$G$$V_1$$N/2-0.01$$V_1$$S$$T$$V_1$

Jeśli pozwolisz cyklowi powtarzać wierzchołki, ale nie krawędzie, uważam, że nadal jest NP-kompletny (przez podobne zmniejszenie, ale dzielenie każdego wierzchołka na skierowaną krawędź ( v , v ′ ) w standardowy sposób).$v$$(v,v')$

Zakładam, że twoje dane wejściowe są grafem ukierunkowanym; Nie wiem, jak to zrobić w przypadku niekierowanej sprawy.

Wykonaj kopii zestawu wierzchołków wykresu, gdzie n jest liczbą wierzchołków na wykresie. Zastąpić każdą krawędź z u do v w oryginalnym wykresie krawędziami, które wykraczają od skopiować I od U skopiować I + 1 od v , dla wszystkich wyborów I . Dodatkowo, jeśli u należą do określonego wierzchołka zestawu, ale nie inaczej, obejmują również krawędź, która przechodzi od kopii i o u skopiować 0 o V .$n$$n$$u$$v$$i$$u$$i+1$$v$$i$$u$$i$$u$$0$$v$

Cykle na rozwiniętym wykresie wszystkie są projektowane z powrotem do cykli na oryginalnym wykresie, ale każdy cykl na rozwiniętym wykresie zawiera jeden z określonych wierzchołków (w przeciwnym razie nie można przejść przez warstwy ekspansji), więc oryginalny wykres zawiera cykl ujemny zawierający określony wierzchołek w rozwiniętym wykresie zawiera dowolny cykl ujemny.