Złożoność znalezienia maksymalnej liczby zestawów rozłącznych parami

Załóżmy, że mam $P$ zestawy z elementami zaczerpniętymi z $r$możliwe. Każdy zestaw ma rozmiar$n$ ($n<r$), gdzie zestawy mogą się nakładać. Chcę ustalić, czy następujące dwa problemy są NP-zupełne, czy nie:

Problem A. Czy są$M$ ($1 \le M \le P$) odrębne zestawy w obrębie$P$ zestawy (tzn. ich skrzyżowanie parami jest puste)?

Problem B. Teraz$k$ ($k<n$) elementy można wybierać z każdego zestawu. Są tam$L$ ($1 \le L \le P$) różne zestawy wielkości$k$ każdy w obrębie $P$zestawy? Pamiętaj, że tylko jeden zestaw$k$ elementy można pobrać z każdego zestawu $n$ elementy.

Uwaga : Interesuje mnie głównie przypadek, w którym$k,n$ są naprawione ($n \ge 2, k \ge 2$).

Myślę, że Problem A można uznać za problem $n$-mundur $r$-partialowy problem dopasowania hiper-grafu. Oznacza to, że mamy elementy$r$ jako wierzchołki, a każda hiper-krawędź zawiera podzbiór $n$ wierzchołki wykresu.

1. w $n$-mundur $r$-partite problem dopasowania hiper-grafu NP-zupełny?

2. Myślę, że problem B jest równoważny znalezieniu liczby wyraźnych hiper-krawędzi liczności $k$ zaczerpnięte z hiper-krawędzi kardynalności $n$. Czy ta wersja jest ograniczona (w tym sensie, że każda$k$- zestaw liczności jest pobierany z wcześniej wybranego zestawu $n$ elementy, a nie wzięte arbitralnie $r$ elementy) problemu A NP-complete?

Przykład ($n=3,r=5, P=3$):

$A=\{1,2,3\}$, $B=\{2,3,4\}$, $C=\{3,4,5\}$

Gdyby $k=n=3$, jest tylko $M=1$ jeden odrębny zestaw, który jest $A$ lub $B$ lub $C$, ponieważ każda z par $(A,B)$, $(A,C)$, $(B,C)$ ma niepuste skrzyżowanie.

Gdyby $k=2$, mamy $L=2$ odrębne zestawy: jedno rozwiązanie jest $\{1,2\}$, $\{3,4\}$ (podzbiory z $A$ i $B$).

Jest to szczególny przypadek problemu maksymalnego upakowania zestawu i oba problemy A i B są NP-Complete . Zauważ, że problem jest po prostu pasującym problemem, jeśli$n=2$ i jest również łatwe, jeśli $n=1$. Więc założę$n \ge 3$.

Zamiast zadawać pytanie,

Są tam $M$ zestawy rozłączne wśród $P$ zestawy?

Zadajmy następujące pytanie

Jaką maksymalną liczbę rozłącznych zestawów możemy uzyskać z $P$ zestawy?

Oczywiste jest, że jeśli na drugie pytanie można odpowiedzieć w czasie wielomianowym, to tak samo jest pierwsze, ponieważ wszystko, co musimy zrobić, to porównać tę maksymalną wartość z $M$i wyślij TAK, jeśli$M$jest mniejsza lub równa temu maksimum, a NIE w przeciwnym razie.

Ponadto, jeśli na pierwsze pytanie można odpowiedzieć w czasie wielomianowym, to drugie też jest, ponieważ możemy użyć wyszukiwania binarnego na $M$ i uzyskaj odpowiedź na drugie pytanie i dodaj tylko współczynnik $O(\log{M})$

Możemy zatem stwierdzić, że oba pytania są równoważne. tzn. pytanie 1 jest rozwiązaniem wielomianu, jeśli tylko pytanie 2 również jest.

Oczywiste jest również, że problemy występują w NP, ponieważ możemy łatwo zweryfikować, że $M$ zestawy wyprowadzane są rozłączne.

Pytanie brzmi zatem, w jaki sposób zredukować do tego znany problem NP-Hard? W tym celu zmniejszamy problem maksymalnego zestawu pakowania . Po prostu skupię się na problemie A, ponieważ problem B można łatwo wykazać jako trudny poprzez ustawienie$k=n-1$

Rozważ dowolne wystąpienie problemu z maksymalnym zestawem pakowania $T$. Należy zauważyć, że jedyną różnicą między problemem A a pierwotnym problemem maksymalnego upakowania zestawu jest to, że w przypadku problemu A rozmiar zestawu musi być równy. Pozwolić$t$ być maksymalną licznością spośród wszystkich zbiorów w $T$. Jeśli każdy zestaw$T$ mają tę samą liczność, jesteśmy skończeni, a problem z zestawem obejmuje dokładnie problem A. Załóżmy, że dla jakiegoś zestawu $S_i \in T$, mamy $|S_i| < t$. Po prostu dodajemy$(t-|S_i|)$ elementy do $S_i$ które nie są elementami żadnego zestawu w $T$. Powtarzamy ten proces, aż wszystkie zestawy$S_i \in T$mieć ten sam rozmiar. Oczywiste jest, że dodanie nowych elementów w ten sposób nie zmienia wielkości maksymalnej liczby zestawów rozłącznych.

Więc jeśli możemy rozwiązać problem $A$ w czasie wielomianowym możemy rozwiązać problem maksymalnego upakowania zestawu w czasie wielomianowym, ponieważ wszystko, co musimy zrobić, to usunąć dodatkowe elementy, które dodaliśmy, a to nie zmienia rozmiaru maksymalnej liczby rozłącznych zestawów w $T$.

EDYCJA - niektóre dodatkowe informacje o problemie B

Załóżmy, że problem B ma wielomianowe rozwiązanie czasowe, rozważmy teraz dowolną instancję $T$ problemu A z $n$elementy na zestaw. Teraz dodajemy element fikcyjny$d$ do każdego zestawu $T$. Zadajemy teraz następujące pytanie.

Jaką maksymalną liczbę rozłącznych zestawów możemy uzyskać, biorąc $n$ elementy z każdego zestawu?

Teraz wiemy, że spośród zestawów maksymalnie, jeden z nich może zawierać element obojętny, dlatego jeśli odpowiedź otrzymamy jako maksimum to $M$, następnie rzeczywista maksymalna liczba zestawów w instancji $T$ (nasz pierwotny problem A) też jest $M$ lub $(M-1)$, ale daje to stałe przybliżenie współczynnika dla maksymalnego upakowania zestawu. Takie przybliżenie jest możliwe tylko wtedy, gdy$P=NP$. Problem B jest więc trudny.