Jaka jest następująca odmiana zestawu Cover Cover?

Jaka jest następująca odmiana na okładce zestawu jako?

Biorąc pod uwagę zbiór S, zbiór C podzbiorów S i dodatnią liczbę całkowitą K, czy istnieją zestawy K w C, tak że każda para elementów S leży w jednym z wybranych podzbiorów.

Uwaga: Nietrudno dostrzec, że ten problem jest NP-Complete: Biorąc pod uwagę normalny problem z ochroną zestawu (S, C, K), wykonaj trzy kopie S, powiedzmy S ', S' 'i S' '', następnie utwórz swoje podzbiory jako S '', | S | podzbiory postaci {a '} U {x in S' '| x! = a} U {a ''}}, | S | podzbiory postaci {a ''} U {x in S '| x! = a} U {a ''}}, {a ', a' '| a w C_i}. Następnie możemy rozwiązać problem pokrycia zestawu za pomocą K podzestawów iff możemy rozwiązać problem pokrycia zestawu za pomocą K + 1 + 2 | S | podzbiory.

Uogólnia to na potrójne itp. Chciałbym nie być w stanie zmarnować połowy strony, co to potwierdza, i prawdopodobnie nie jest to wystarczająco oczywiste, by uznać to za trywialne. Z pewnością jest wystarczająco użyteczne, aby ktoś to udowodnił, ale nie mam pojęcia, kto ani gdzie.

Czy jest też dobre miejsce, aby szukać wyników NP-Completeness, których nie ma w Garey i Johnson?

Aby odpowiedzieć na drugie pytanie, kompendium wyników twardości NP Kahna-Crescenzi jest cennym źródłem wyników twardości, a także obejmuje wiele wariantów podstawowych problemów G&J. T entry on dla zadanej okładce jest dobrym tego przykładem.

Wygląda na to, że uogólniasz zestaw okładek, aby uwzględnić nie tylko elementy S, ale każdy podzbiór rozmiaru M S. Możemy opisać problem bardziej ogólnie:

„Biorąc pod uwagę zbiór S, zbiór C podzbiorów S i dodatnią liczbę całkowitą m, jaka jest najmniejsza liczba elementów C, tak że każdy podzbiór M wielkości M leży w jednym z wybranych elementów C?”

W rzeczywistości wydaje mi się to dość oczywistym uogólnieniem pokrycia zestawu, a nie takim, którego trzeba poświęcić na sprawdzenie NP-kompletności poza jedną linią. W końcu wybranie m = 1 przywraca pierwotny problem z zestawem okładek. Być może ta bardziej ogólna formuła jest wystarczająca dla twoich celów, aby uniknąć konieczności zagłębiania się w szczegóły?

Twoje pytanie dotyczące zaktualizowanego zestawu wyników kompletności NP jest dobre i zasługuje na własne pytanie. Crescenzi i Kann Zebraliśmy użyteczne kompendium on-line tutaj .

Po drugie, jest mało rozpowszechniony, ale Steven Skiena, Podręcznik projektowania algorytmów, jest często przydatnym pierwszym krokiem do rozwiązania wielu problemów i jest częściowo dostępny online .