В задаче ПОКРЫТИЕ МНОЖЕСТВА дано семейство \(\mathcal F=\{S_1,\ldots,S_m\}\) подмножеств универсума \(S\), причём их объединение равно \(S\), и число \(h\). Требуется определить, можно ли выбрать не более \(h\) множеств, объединение которых равно всему
Задача NP-полна. В курсе NP-трудность доказывается сведением VERTEX COVER к SET COVER: универсумом делают рёбра исходного графа, а каждой вершине сопоставляют множество инцидентных ей
Что важно запомнить
- Сертификат — список не более \(h\) выбранных подмножеств. Проверить их объединение можно полиномиально.
- В сведении из VERTEX COVER универсум \(S\) равен множеству рёбер
- Вершине \(v\) соответствует множество всех рёбер, инцидентных \(v\).
- Выбор не более \(l\) вершин, покрывающих все рёбра, эквивалентен выбору не более \(h=l\) соответствующих подмножеств, покрывающих \(S\).
Сведение VERTEX COVER к SET COVER
Пусть дан граф \(G=(V,E)\) и число \(l\). Строим экземпляр SET COVER:
- универсум \(S=E\);
- для каждой вершины \(v_j\in V\) множество \(S_j=\{e\in E: e\text{ инцидентно }v_j\}\);
- параметр \(h=l\).
Если \(R=\{v_{i_1},\ldots,v_{i_r}\}\), \(r\le l\), является вершинным покрытием, то каждое ребро инцидентно хотя бы одной вершине из \(R\). Следовательно, \(S_{i_1}\cup\cdots\cup S_{i_r}=E=S\), то есть соответствующие множества дают покрытие универсума.
Обратно, если не более \(h\) множеств \(S_{i_1},\ldots,S_{i_r}\) покрывают весь универсум \(E\), то каждое ребро принадлежит хотя бы одному из них и потому инцидентно одной из вершин \(v_{i_1},\ldots,v_{i_r}\). Эти вершины образуют вершинное покрытие размера не более
Построение семейств инцидентных рёбер имеет полиномиальный размер, поэтому \(VERTEX\ COVER\prec SET\ COVER\). Вместе с принадлежностью \(NP\) получаем NP-полноту.
Частые ошибки
- Путать decision SET COVER с оптимизационной задачей поиска минимального числа множеств. NP-полнота здесь относится к вопросу «существует ли покрытие размера не более \(h\)?».
- В сведении брать универсумом вершины графа. В конструкции курса универсумом служит именно множество рёбер.
- Считать, что множества \(S_j\) должны быть непересекающимися. Для покрытия пересечения допустимы и обычны.
