Czy Logical Min-Cut NP-Complete?

Definicja problemu Logical Min Cut (LMC)

Załóżmy, że jest nieważonym wykresem, i są dwoma wierzchołkami , a jest osiągalne z . LMC Problem badania jak możemy nieosiągalny ze poprzez usunięcie niektórych krawędziach następujących następujące ograniczenia:$G = (V, E)$$s$V t s t s $t$$V$$t$$s$$t$$s$$G$

1. Liczba usuniętych krawędzi musi być minimalna.
2. Nie możemy usunąć każdej krawędzi wyjściowej żadnego wierzchołka (tzn. Żaden wierzchołek z krawędziami wychodzącymi nie może mieć usuniętych wszystkich krawędzi wychodzących).$G$

To drugie ograniczenie nazywa się usuwaniem logicznym. Szukamy więc logicznego, minimalnego usunięcia niektórych krawędzi tak aby był nieosiągalny dla .t $G$$t$$s$

Próby rozwiązania

Jeśli zignorujemy logiczne ograniczenie usuwania problemu LMC, będzie to problem minimalnego cięcia w nieważonym digrafie , więc będzie on rozwiązywalny wielomianowo (twierdzenie o maksymalnym przepływie dla minimalnego przepływu).$G$

Jeśli zignorujemy minimalne ograniczenie usuwania problemu LMC, to będzie znowu rozwiązywalne wielomianowo w DAG: znaleźć wierzchołek takie, że jest osiągalny z i nie jest osiągalny z . Następnie rozważ ścieżkę która jest dowolną ścieżką od do . Teraz rozważ ścieżkę jako podrozdział : odpowiedzią będzie każda krawędź wyjściowa podrozdziału . Oczywiste jest, że wierzchołek może być znaleziony przez DFS w w czasie wielomianowym. Niestety ten algorytm ogólnie nie działak s t k p s k p G p k $k$$k$$s$$t$$k$$p$$s$$k$$p$$G$$p$$k$$G$ dla dowolnego ukierunkowanego wykresu.

Próbowałem rozwiązać problem LMC za pomocą techniki programowania dynamicznego, ale liczba stanów wymaganych do rozwiązania problemu stała się wykładnicza. Co więcej, próbowałem zredukować niektóre problemy z NP-Complete, takie jak 3-SAT, max2Sat, max-cut i kliknięcie do problemu LMC, ale nie udało mi się znaleźć redukcji.

Osobiście uważam, że problem LMC jest NP-Complete, nawet jeśli jest binarnym DAG (tj. DAG, w którym żaden węzeł nie ma stopnia większego niż 2).$G$

pytania

1. Czy problem LMC NP-Complete znajduje się w dowolnym wykreślniku ? (główne pytanie)$G$
2. Czy problem LMC NP-Complete występuje w dowolnym DAG ?$G$
3. Czy problem LMC NP-Complete występuje w dowolnym binarnym DAG ?$G$

Niech G = (V, E) będzie ważonym DAG, s i t będą dwoma wierzchołkami G, a LSTMC = (G, s, t) będzie wystąpieniem logicznego problemu st min-cut. Oczywistym jest, że problemem LSTMC jest NP. Teraz powinniśmy pokazać, że LSTMC jest NP-Hard. Zmniejszamy problem zestawu uderzeń do problemu LSTMC. Niech S = {s1, s2, ..., sn} będzie podanymi zbiorami, a {a1, a2, ..., am} będzie sumą wszystkich zbiorów. Biorąc pod uwagę liczbę k1, problem decyzyjny problemu trafienia zestawu określa, czy istnieje zestaw A z elementami k1 takimi, że każdy element S (każdy zestaw si st i = 1..n) zawiera co najmniej jeden element A. oznacza problem zestawu uderzeń jako HS (S). Konstruujemy ważoną DAG G 'z zestawu S według algorytmu HS2LSTMC. Algorytm ten uważa s za wierzchołek źródłowy DAG G ′. Dla każdego zestawu si HS st i = 1..n algorytm uwzględnia odpowiedni wierzchołek, si i dodaje krawędź o nieskończonej wadze od s do każdego si. Następnie dla każdego elementu aj unii zbiorów wejściowych st j = 1..m algorytm uwzględnia odpowiedni wierzchołek, aj i dodaje krawędź o zerowej wadze z każdego si do dowolnego aj st aj ∈si w HS. Na koniec algorytm bierze pod uwagę dwa końcowe wierzchołki zwane t i k i dodaje dwie krawędzie z każdego aj st j = 1..m do obu końcowych wierzchołków. Oczywiste jest, że G 'można wykonać w czasie wielomianowym.

Teraz powinniśmy wykazać, że HS (S) ma odpowiedź z elementami k1 wtedy i tylko wtedy, gdy LSTMC = (G ′, s, t) ma odpowiedź z pewnymi logicznie usuniętymi krawędziami, tak że suma wag usuniętych krawędzi wynosi k1.

Dla uproszczenia wykonujemy tę część dowodu, podając przykład:

Na poniższym rysunku załóżmy, że S = {s1, s2, s3} tak, że s1 = {1, 2, 3}, s2 = {1, 4} i s3 = {2, 5}. Ryc. 2 pokazuje ważoną DAG G 'problemu LSTMC odpowiadającego problemowi zestawu uderzeń HS (S). W tym przykładzie zestaw A, a mianowicie suma wszystkich elementów S, wynosi A = {1, 2, 3, 4, 5}. Mamy | S | = 3 i | A | = 5. Ten przykład pokazuje, jak dowolną instancję problemu zestawu uderzeń można rozwiązać za pomocą konkretnej instancji problemu logicznego st min-cut w ważonej DAG. Jeśli obliczymy odpowiedź na LSTMC = (G ′, s, t) i rozważymy te usunięte krawędzie odpowiedzi, które są w postaci (aj, t) o nazwie E1 (1 ≤ j ≤ m), wówczas zestaw ogona E1 jest odpowiedzią na HS (S). Odpowiedzią na problem LSTMC jest zestaw zboczy E1 = {(s1, 2), (s1, 3), (s2, 4), (s3, 5), (1, t), (2, t)}. Tak więc zestaw ogona podzbioru E2 = {(1, t), (2,

Oto (próba) algorytm wielomianowy czasu dla LKM arbitralne binarny DAG .$G$

To odpowiada na pytanie nr 3. (Przepraszam za niechlujny napis z góry. :))

Na początek wyrzuć „na zawsze” każdy wierzchołek nieosiągalny od . Nie dbamy o to, ponieważ nie są one częścią żadnej ścieżki - .s $s$$s$$t$

Następnie zdefiniuj podagony DAG i , początkowo puste. Następnie przez wszystkie wierzchołki ,B v ∈ G - { s , t $A$$B$$v \in G-\{s, t\}$

Sprawdź, czy istnieje ścieżka od do . Jeśli tak, dodaj do . Jeśli nie, należy dodać do .t v A v $v$$t$$v$$A$$v$$B$

Niech krawędzie i będą krawędziami indukowanymi przez wierzchołki w obrębie każdego zestawu (na razie zignoruj ​​wszelkie krawędzie od do , od do oraz od do ; zauważ również, że nie ma żadnych krawędzi od do o budowa).B s A A t A B B $A$$B$$s$$A$$A$$t$$A$$B$$B$$t$

Następnie obliczyć przechodni zamknięcie . Mianowicie, jesteśmy zainteresowani w znalezieniu jakiś zbiór wierzchołków , które są „listki” w sub-DAG .{ a ∗ } $A$$\{a^*\}$$A$

Napraw dowolne takie . Zauważ, że musi być skierowana krawędź od do . Wynika to z faktu, że z założenia (i) istnieje ścieżka - przez , (ii) nie ma ścieżek od do , oraz (iii), ponieważ sam jest DAG i jest liściem , nie ma ścieżki od przez inny wierzchołek do .a ∗ t s t a ∗ a ∗ B A a ∗ A a ∗ A $a^*$$a^*$$t$$s$$t$$a^*$$a^*$$B$$A$$a^*$$A$$a^*$$A$$t$

Teraz musi istnieć skierowana krawędź od każdego wierzchołka w do jakiegoś wierzchołka w , lub niektóre z mają pojedynczą krawędź do . W obu przypadkach możemy usunąć dowolną krawędź .B { a ∗ } t a ∗ → $\{a^*\}$$B$$\{a^*\}$$t$$a^*\rightarrow t$

Jeśli= 1, albo musimy usunąć krawędź z unikalnego , lub istnieje wierzchołek wcześniej na ścieżce - zawierającej która ma dwie ścieżki do - jednej przez i jeden bezpośrednio. W przypadku, gdy ten ostatni może się utrzymać, rejestrujemy i postępujemy „zachłannie wstecz” (szczegóły na ten temat poniżej).$|\{a^*\}|$$a^*\rightarrow t$$s$$t$$a^*$$t$$a^*$$a^*\rightarrow t$

Jeśli> 1, musimy albo usunąć wszystkie krawędzie z , albo istnieje pewna liczba krawędziwcześniej w przejściowym zamknięciu które odłączają wszystkie ścieżki od do do .$|\{a^*\}|$$\{a^*\}\rightarrow t$$k < |\{a^*\}|$$A$$s$$\{a^*\}$$t$

Tutaj wykorzystujemy fakt, że wykres jest binarnym DAG.$G$

Rozważ zestaw poprzedników . Ponieważ każdy z tych wierzchołków ma maksymalnie dwa stopnie, są dokładnie trzy przypadki:$\{a^*\}$

Przypadek 1. prekursor ma na zewnątrz krawędzią do pewnego wierzchołka w oraz na zewnątrz krawędzią do pewnego wierzchołka w .$\{a^*\}$$B$

W tym przypadku nie ma znaczenia, czy usuwamy krawędź z poprzednika do wierzchołka w czy krawędź od wierzchołka w do . Dlatego możemy „pominąć” ten wierzchołek (i sprawdzić, czy ścieżka wsteczna łączy się ze ścieżką innego wierzchołka w ).$\{a^*\}$$\{a^*\}$$t$$\{a^*\}$

Przypadek 2. Poprzednik ma krawędź wierzchołka w i inny poprzednik .$\{a^*\}$$\{a^*\}$

W takim przypadku musimy albo usunąć obie krawędzie z do , albo możemy usunąć pojedynczą wcześniejszą krawędź ścieżki od do poprzednika, który rozłącza obie ścieżki.$\{a^*\}$$t$$s$

Przypadek 3. Poprzednik ma krawędź do dwóch wierzchołków w .$\{a^*\}$

Jest to identyczne jak w przypadku 2. Nie ma znaczenia, czy usuwamy jedną z krawędzi tego poprzednika i odpowiadające im inne krawędzie z do , czy obie krawędzie z do . Chcemy tylko wiedzieć, czy możemy odłączyć ścieżkę od przez tego poprzednika do jedną krawędzią wcześniej na ścieżce od do poprzednika.$\{a^*\}$$t$$\{a^*\}$$t$$s$$t$$s$

Podsumowując, gdy przeglądamy wstecz przez poprzedników w przejściowym zamknięciu , możemy zachłannie śledzić „najlepsze jak dotąd” wybory. Oznacza to, że na każdym etapie mamy oczywisty wybór, który polega na usunięciu pewnej liczby krawędzi, ale chcemy poczekać, aby zobaczyć, czy dostępna jest lepsza opcja. Po znalezieniu lepszej opcji możemy „zapomnieć” o poprzedniej opcji. Dlatego wystarczy chciwy wybór na każdej warstwie poprzedników (o ile czekamy do końca, aby dokonać wyboru).$A$

Dlatego przy niektórych podstawowych zapamiętywaniach czas i przestrzeń złożoności tego procesu wydają się wynosić najwyżej . Pomija to fakt, że chociaż możemy lokalnie / chciwie zidentyfikować, kiedy znaleźliśmy „tańszy wybór”, z góry nie jest jasne, które wcześniej zarejestrowane krawędzie należy usunąć. Dlatego rejestrujemy kolejność sprawdzania krawędzi podczas pracy. Po znalezieniu lepszej opcji powtarzamy wyszukiwanie do tego momentu, aby znaleźć wcześniej zarejestrowane krawędzie do usunięcia. Całkowity czas złożoności tego etapu wynosi a złożoność przestrzeni .$O(|E|)$$O(|E|^2)$$O(|E|)$

W sumie złożoność czasu wynosi dla inicjalizacji plus dla zamknięcia przechodniego plus dla poszukiwanie. Całkowity czas wynosi .$O(|V|\cdot(|V|+|E|))$$O(|V|^3)$$O(|E|^2)$$O(|V|^2+|E||V|+|V|^3+|E|^2) = {\bf O(|V|^3+|E|^2)}$

Po zakończeniu procesu otrzymujemy minimalny zestaw krawędzi wymagany do odłączenia od , zachowując co najmniej jeden brzeg każdego wierzchołka na wykresie (lub odkrywamy, że rozwiązanie jest niemożliwe po drodze i przerywamy).$s$$t$