Как называется следующий вариант Set Set?

15

Как называется следующий вариант обложки набора?

Для заданного набора S, набора C подмножеств S и целого положительного числа K существуют ли K наборов в C, так что каждая пара элементов S лежит в одном из выбранных подмножеств.

Примечание. Нетрудно понять, что эта проблема является NP-полной: учитывая нормальную проблему покрытия множества (S, C, K), сделайте три копии S, скажем S ', S' 'и S' '', затем создайте свои подмножества как S '' ', | S | подмножества вида {a '} U {x в S' '| x! = a} U {a '' '}, | S | подмножества вида {a ''} U {x в S '| x! = a} U {a '' '}, {a', a '' | в C_i}. Тогда мы можем решить проблему покрытия множеств с K подмножествами, если только мы можем решить проблему покрытия пар с помощью K + 1 + 2 | S | подмножества.

Это обобщается на тройки и т. Д. Я хотел бы иметь возможность не тратить половину страницы, доказывая это, и это, вероятно, не достаточно очевидно, чтобы отклонить как тривиальный. Конечно, достаточно полезно, чтобы кто-то это доказал, но я понятия не имею, кто и где.

Кроме того, есть ли хорошее место для поиска результатов NP-полноты, которых нет в Garey и Johnson?

np-hardness set-cover cc.complexity-theory deinst
источник

Ответы:

7

Чтобы ответить на ваш второй вопрос, сборник результатов по твердости по NP-Кану-Крещенци является ценным источником результатов по твердости, а также охватывает многие варианты основных проблем G & J. T он вход для набора крышки является хорошим примером этого.

Суреш Венкат
источник
2
Я видел это раньше, и да, это помогает, но даже не начинает царапать поверхность того, что было доказано NP-Complete. Чтобы привести другой пример, мне потребовалось гораздо больше времени, чтобы найти доказательство Уехары, что покрытие вершин было NP-полным на трехсвязном кубическом плоском графе, чем мне потребовалось, чтобы доказать это. (Ее доказательство было намного чище, чем мое.)
2010 г.
7

Похоже, вы обобщаете набор покрытия для рассмотрения не только элементов S, но и каждого подмножества размера-M S. Мы можем сформулировать проблему в более общем виде:

«Учитывая набор S, набор C подмножеств S и положительное целое число m, каково наименьшее количество элементов C, такое, что каждое подмножество размера M в S лежит в одном из выбранных элементов C?»

Это на самом деле кажется мне довольно очевидным обобщением набора покрытий, и вам не нужно тратить время на доказательство NP-завершения за одну строчку. В конце концов, выбор m = 1 восстанавливает исходную проблему покрытия набора. Возможно, эта более общая формулировка достаточно хороша для ваших целей, чтобы избежать необходимости вдаваться в детали?

Ваш вопрос об обновленном наборе результатов NP-полноты является хорошим и заслуживает отдельного вопроса. Crescenzi и Kann собрали полезный сборник онлайн здесь .

Во-вторых, оно вряд ли распространено, но Руководство по разработке алгоритмов Стивена Скиены часто является полезным первым шагом для решения большого количества проблем и частично доступно в Интернете .

Ананд Кулкарни
источник
Меня интересует только m = 2. Может быть, есть доказательство в одну строку, но это доказательство ускользает от меня. Я полагаю, что четко изложил это во втором предложении вопроса.
2010 г.
Извинения; Я не хотел предполагать, что в парном случае есть короткое доказательство! Предложенное мною однострочное доказательство приведено только в общем варианте задачи: «частный случай m = 1 восстанавливает стандартное покрытие набора». Как вы указали, доказательство в парном случае очевидно (вводите фиктивные элементы и наборы в стандартное покрытие наборов для генерации покрытия парных наборов), но да, потребуется несколько строк, чтобы показать его формальность. Я посмотрю, смогу ли я найти какие-либо ссылки на это в литературе.
Ананд Кулькарни