[мм, алгоритмы] является ли NP-трудной задача... - Public forum of MSU united student networks

Дано конечное множество M и семейство S его подможеств (покрытие). Требуется выбрать из S максимальное (по мощности получаемого объединения) семейство непересекающихся подмножеств K. Мощность самого K значения не имеет. Мощности M и S одного порядка.

На языке графов: выделить семейство независимых вершин (не соединены ребрами) так, чтобы число ребер, инцидентных вершинам, было максимально. Заметте, что это НЕ задача о максимальном независимом множестве вершин, так как само число вершин роли не играет, максимизируется число "покрываемых" ребер.

Есть также близкая по постановке задача о выделении наименьшего подпокрытия, она NP-полна (сводится к наименьшему вершинному покрытию графа). Здесь же, во первых, не требуется, чтобы K в объединении давало M, нужно лишь, чтобы оно "накрывало" как можно больше элементов. Во-вторых, подмножества в K дизъюнктны. В третьих, число подможеств не имеет значения.

Если вопрос оказался простым, то задача может быть усложнена так: подможества из K имеют право пересекаться, но так, что каждый элемент входит не более, чем в k подможеств (на языке графов - каждое ребро инцедентно не более, чем k выбранным вершинам). Предполагается, что k много меньше мощности всего M.

Именно в такой постановке эта задача возникла на практике - составление "расписания" для параллельного обхода сайтов роботом: нельзя лезть на один сайт более чем k процессами одновременно, есть множество S групп сайтов, группу надо ставить или не ставить в очередь целиком, M - объединение всех групп. Требуется найти максимальный (по числу сайтов) набор групп K, которые можно обходить одновременно. M и S содержат порядка десятков миллионов элементов, k = 10.