Изменения

Наивный жадный алгоритм не работает, потому что неясно, как проверять множество на независимость в <tex>M</tex>. Пусть <tex>I_i \in \mathcal{I}_i</tex>, для <tex>i = 1\ldots k</tex> с <tex>I_i \cap I_j = \emptyset</tex>, если <tex>i \neq j</tex>. Определим [[Граф замен|граф замен]]: для каждого <tex>M_i</tex> построим [[Основные определения теории графов#defBiparateGraph|двудольный ориентированный граф]] <tex>D_{M_i}(I_i)</tex> так, что в левой доле находятся вершины из <tex>I_i</tex>, а в правой — вершины из <tex>S \setminus I_i</tex>. Построим ориентированные ребра из <tex>y \in I_i</tex> в <tex>x \in S \setminus I_i</tex>, при условии, что <tex>(I_i \setminus y) \cup x \in \mathcal{I}_i</tex>.