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

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

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