Dany jest zbiór \(\displaystyle{ B =\left\{ b_{1},...,b_{3k} \right\}}\) oraz rodzina \(\displaystyle{ S =\left\{ S_{1},...,S_{n} \right\}}\) podzbiorów \(\displaystyle{ B}\) taka, że dla każdego \(\displaystyle{ 1 \le i \le n, \left| S_{i} \right|=3}\), oraz dla każdego \(\displaystyle{ 1 \le j \le 3k}\) element \(\displaystyle{ b_{j}}\) występuje w dokładnie dwóch zbiorach z \(\displaystyle{ S}\).
Czy istnieje \(\displaystyle{ I \subseteq \left\{ 1,...,n\right\}}\) taki, że \(\displaystyle{ \left| I \right|=k}\) oraz \(\displaystyle{ \bigcup_{i \in I}^{S_{i}}=B}\).
Czy dla problemu istnieje algorytm wielomianowy, czy problem jest NP-zupełny, czy CONP-zupełny.
Również poszukuję jakichś wskazówek, jak się za to zabrać.
Jedyne co udało mi się do tej pory wymyślić, to że to jest zawężenie dziedziny wejścia w problemie X3C, który można wykazać że jest NP-zupełny.
Problem jest taki, że to nic nie daje.-- 14 cze 2016, o 00:15 --Dla potomnych: Problem ten jest równoważny dwukolorowaniu grafu takiego że wierzchołkami są podzbiory z rodziny \(\displaystyle{ S}\), a krawędź między wierzchołkami istnieje wtedy, jeżeli maja jakiś wspólny element.
