Czy to trudne NP? Nie mogę tego udowodnić.

11

Mam problem i myślę, że jest to trudny NP, ale nie mogę tego udowodnić.

Oto wykres warstw, w którym warstwa 0 jest najwyższą warstwą, a warstwa L najniższą.

istnieje pewna ukierunkowana krawędź między warstwami, gdzie krawędź (A, B) wskazuje, że węzeł A może [pokrywać] węzeł B. A kiedy A może obejmować B, każdy węzeł na dowolnej ścieżce od A do B może obejmować B, B może obejmować samo.

Wreszcie nadchodzi zestaw węzła S. Muszę wybrać inny zestaw węzła ANS i upewnić się, że dla każdego węzła q w S istnieje węzeł pw ANS, a p obejmuje q.

Każdy węzeł wiąże się z pewnym kosztem i muszę zminimalizować całkowity koszt zestawu ANS.

Czy to trudny NP? Tak mi się wydaje, ale nie mogę tego udowodnić.

Czy mógłbyś mi pomóc?

Dziękuję Ci bardzo.

graphs np qin.sun
źródło
koszt węzła z górnej warstwy jest droższy na dowolnej ścieżce na wykresie.
Tak, to naprawdę wydaje się trudne NP. Spójrz na dość podobny problem z minimalną ochroną zestawu. en.wikipedia.org/wiki/Set_cover_problem
Czy jest jakieś ograniczenie w ukierunkowanej krawędzi, takie jak krawędzie łączące tylko węzeł w wyższej warstwie z węzłem w niższej warstwie? Czy mogę wyjaśnić, że między węzłami na tej samej warstwie nie może być żadnej krawędzi?
justhalf
@ justhalf Nie, nie ma krawędzi między węzłami na tej samej warstwie. Dziękuję :)
qin.sun

Odpowiedzi:

6

Tak, ten problem jest zdecydowanie trudny NP. Publikuję tę odpowiedź, ponieważ potrzebujesz dowodu.

Jeśli podążasz za tym linkiem http://en.wikipedia.org/wiki/Set_cover_problem , to mówi, że optymalizacyjna wersja minimalnego problemu z zestawem obejmuje NP-Hard.

Problem w łączu:

Biorąc pod uwagę zestaw elementów {1,2, ..., m} (zwany wszechświatem) i zbiór S zestawów n, których suma jest równa wszechświatowi, problemem pokrycia zestawu jest identyfikacja najmniejszego podzbioru S, którego suma jest równa wszechświat. Rozważmy na przykład wszechświat U = {1, 2, 3, 4, 5} i zestaw zbiorów S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Najwyraźniej związek S jest U. Jednak możemy objąć wszystkie elementy następującą, mniejszą liczbą zestawów: {{1, 2, 3}, {4, 5}}

Możesz to powiązać z problemem w następujący sposób:

S to zbiór węzłów obejmujących co najmniej jeden węzeł w zestawie wejściowym. Można to znaleźć, przeprowadzając DFS na węzłach zestawu danych wejściowych z odwróconym kierunkiem krawędzi.

Teraz problem opisany w łączu jest szczególnym przypadkiem twojego problemu, w którym koszt każdego węzła jest równy i chcesz po prostu zminimalizować liczbę węzłów (zestawów).

Dlatego twój problem jest jeszcze trudniejszy do rozwiązania w ogólnym przypadku i dlatego jest trudny.

Abhishek Bansal
źródło
Myślę, że jest to prawdą w definicji OP, ale nigdy też nie określa, czy można „zakryć” węzeł krawędzią na tej samej warstwie co ten węzeł. W takim przypadku problem wydaje się nieco inny. W przeciwnym razie, jeśli możesz pokryć węzeł tylko przez krawędź z wyższej warstwy, to rzeczywiście wydaje się to równoznaczne z ustawieniem optymalizacji pokrycia
roliu
@roliu Jak ważne byłoby, czy te same węzły warstwowe mogą zostać pokryte, czy nie. Problem, jak rozumiem, polega na tym, że mamy ukierunkowany wykres ze ścieżką między węzłem A do B, co oznacza, że ​​A obejmuje B.
Hm, nie jestem pewna. To po prostu dziwne, ponieważ nie sądzę, aby prawie żadna z informacji w PO była faktycznie przydatna. Warstwy wydają się nieistotne, podobnie jak przechodniość. W większości czekam, aż OP wyjaśni, że tak naprawdę miał na myśli coś innego. W szczególności możesz pokazać, że jest to nie tylko tak trudne, jak ustalona okładka, ale w rzeczywistości jest równoważne. Ponieważ każde minimalne pokrycie problemu OP będzie zawierać tylko sąsiednie węzły jego zestawu danych wejściowych S. Może są koszty ujemne lub coś w tym rodzaju ...
roliu