Твердость подмножества Set Cover

10

Насколько сложна проблема Set Cover, если число элементов ограничено некоторой функцией (например, ), где - размер экземпляра задачи. Формально,nlognn

Пусть и где и . Насколько сложно решить следующую проблему?F = { S 1 , , S n } S iU m = O ( log n )U={e1,,em}F={S1,,Sn}SiUm=O(logn)

SET-COVER'={<U,F,k>: there exists at most k subsets  Si1,,SikF that cover U}.

Что если ?m=O(n)

Любой результат, основанный на общеизвестных догадках (например, Unique Games, ETH), хорош.

Редактировать 1: Мотивация для этой проблемы заключается в том, чтобы выяснить, когда проблема усугубляется с увеличением . Ясно, что проблема в P, если и NP-hard, если . Какой порог для NP-сложности проблемы?m = O ( 1 ) m = O ( n )mm=O(1)m=O(n)

Редактировать 2: Существует тривиальный алгоритм для его решения за время (который перечисляет все подмножества размера в ). Следовательно, задача не является NP-сложной, если поскольку ETH подразумевает, что не существует алгоритма во времени для любой NP-сложной задачи. проблема (где - размер NP-сложной задачи).m F m = O ( log n ) O ( 2 n o ( 1 ) ) nO(nm)mFm=O(logn)O(2no(1))n

user1297
источник
2
Существует лучший алгоритм для решения проблемы во времени (точнее, числа Белла для ): для каждого разбиения элементов на подмножества проверьте, существует ли входной набор, охватывающий каждое подмножество. Таким образом, при проблема может быть решена за полиномиальное время. Это не совсем отвечает на ваш вопрос о . m m = O ( log n / log log n ) m = O ( log n )mO(m)mm=O(logn/loglogn)m=O(logn)
Дэвид Эппштейн

Ответы:

11

Когда , вы можете использовать динамическое программирование, чтобы найти оптимальное за полиномиальное время. Таблица содержит булевозначные ячейки для каждого и , указывающие, существуют ли наборы, которые покрывают элементов в .T , X{ 0 , , k } X UXm=O(logn)T,X{0,,k}XUX

Когда , скажем, , проблема остается NP-трудной. Для данного экземпляра SET-COVER добавьте новых элементов и новых набора, состоящих из непустых подмножеств новых элементов, включая (когда достаточно велико, ). Также увеличьте на единицу. Новые - это и .mCm=O(n) mx1,,xm(2C - 1 м)2{x1,,xm}m(2C - 1 м)2<2mkm,nm=2mn=n+(2C - 1 м)2mCnmx1,,xm(2C1m)2{x1,,xm}m(2C1m)2<2mkm,nm=2mn=n+(2C1m)2(C1m)2

Юваль Фильмус
источник
В более общем случае, случай является NP-сложным, а случай не является NP-сложным в предположении ETH, поскольку существует алгоритм. m = n o ( 1 ) p o l y ( n , 2 м )m=nO(1)m=no(1)poly(n,2m)
Юваль Фильмус
11

Случай находится в времени, как отметил Ювал, но также обратите внимание, что для вы можете решить проблему в время (полиномиальное время) путем исчерпывающего поиска. Предполагая гипотезу сильного экспоненциального времени (что для CNF-SAT по формулам с переменными и предложениями требуется как минимум времени), эти две временные границы являются «пределом» того, что мы можем ожидать в полиномиальное время, в следующем смысле.n O ( c ) k = O ( 1 ) O ( n km ) N O ( N ) 2 N - o ( N )m=clognnO(c)k=O(1)O(nkm)NO(N)2No(N)

В моей статье SODA'10 с Михаем Патраску мы изучаем существенно изоморфную проблему нахождения доминирующего множества размера в произвольном узловом графе, показывая, что если доминирующее множество можно решить в время для некоторого и , тогда существует временной алгоритм для CNF-SAT для переменных и предложений.n k n k - εknknkεε > 0 2 N ( 1 - ε / 2 ) p o l y ( M ) N Mk2ε>02N(1ε/2)poly(M)NM

Отметив взаимосвязь между окрестностями вершин в экземпляре доминирующего набора и множествами в экземпляре покрытия набора, и изучив редукцию, вы обнаружите, что это сокращение также показывает решение -Set Cover с наборами в юниверсе размера в Время подразумевает алгоритм CNF-SAT для формул CNF с предложениями и переменными, работающими за времени , Для опровержения Сильного ETH достаточно решить CNF-SAT в случае, когда . Следовательно, алгоритм для вашей задачи работает вn m n k - εf ( m ) M N 2 N ( 1 - ε / 2 )f ( M ) M = O ( N ) n k - ε2 m / α ( m ) α ( m )knmnkεf(m)MN2N(1ε/2)f(M)M=O(N)nkε2m/α(m)Время для некоторой неограниченной функции привело бы к неожиданному новому алгоритму SAT.α(m)

Райан Уильямс
источник