Znajdź cykl ujemny z ograniczeniami wierzchołków

11

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\}$

ds.algorithms graph-theory

— Tianyi Cui
źródło

To pytanie jest dość niejasne. Ciężary na czym, krawędziach lub wierzchołkach? Co to jest , czy jest wierzchołkiem czy zbiorem wierzchołków?

{V_{1}, V_{2}, \dots, V_{k}}

$\{V_1, V_2, \dots, V_k\}$

V_{1}

$V_1$

— Yixin Cao

@YixinCao Dzięki za odnotowanie, edytowane: waga na krawędziach, jest wierzchołkiem.

V_{1}

$V_1$

— Tianyi Cui

8

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 . Ale jeśli ma to jakiś składnik, można znaleźć (nie prosty) cykl ujemny zawierający , pobierając wiele kopii cyklu ujemnego i dodając do tych ścieżek do i od pewnego wierzchołka cyklu do . (Całkowity czas znalezienia niejawnej reprezentacji pożądanego cyklu będzie taki sam jak czas znalezienia ujemnego cyklu na ukierunkowanym wykresie, np. $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 do danego ujścia na danym wykresie , nadaj istniejącej krawędzi wagę -1, a następnie dodaj sztuczny wierzchołek z dwiema krawędziami koszt każdy, jeden od do a drugi od do ). $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ź w standardowy sposób). $v$ $(v,v')$

— Neal Young
źródło

2

Podoba mi się ta odpowiedź znacznie lepiej niż moja.

— David Eppstein,

6

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 jest liczbą wierzchołków na wykresie. Zastąpić każdą krawędź z do w oryginalnym wykresie krawędziami, które wykraczają od skopiować od skopiować od , dla wszystkich wyborów . Dodatkowo, jeśli należą do określonego wierzchołka zestawu, ale nie inaczej, obejmują również krawędź, która przechodzi od kopii o skopiować o . $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.

— David Eppstein
źródło

Jeśli oryginalny wykres ma

wierzchołków i

krawędzi, nowo zbudowany wykres będzie miał

wierzchołków i

krawędzi. Znalezienie w nim cykli ujemnych będzie wymagało czasu

, który wydaje się dość duży. Nadal czekam na lepsze rozwiązanie i wielkie dzięki!

n

$n$

m

$m$

n^{2}

$n^2$

n m

$nm$

O (n^{3} m)

$O(n^3m)$

— Tianyi Cui

2

Być może bardziej problematyczne, cykle, które znajdzie, niekoniecznie będą proste. Czy potrzebujesz prostych cykli ujemnych?

— David Eppstein,