Dureté d'un sous-boîtier de Set Cover

10

Quelle est la difficulté du problème Set Cover si le nombre d'éléments est limité par une fonction (par exemple, logn ) où n est la taille de l'instance de problème. Officiellement,

Soit U={e1,,em} et où et . Est-il difficile de décider du problème suivantS iU m = O ( log n )F={S1,,Sn}SiUm=O(logn)

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

Et si ?m=O(n)

Tout résultat basé sur des conjectures bien connues (par exemple, Unique Games, ETH) est bon.

Edit 1: Une motivation pour ce problème est de savoir quand le problème devient difficile à mesure que augmente. Clairement, le problème est dans P si et NP-dur si . Quel est le seuil de dureté NP du problème?mm=O(1)m=O(n)

Edit 2: Il existe un algorithme trivial pour le décider dans le temps (qui énumère tous les sous-ensembles de taille de ). Par conséquent, le problème n'est pas NP-dur si car ETH implique qu'il n'y a pas d'algorithme dans le temps pour tout NP-dur problème (où est la taille du problème NP-difficile).O(nm)mFm=O(logn)O(2no(1))n

user1297
la source
2
Il existe un meilleur algorithme pour décider du problème dans le temps (plus précisément le nombre de Bell pour m ): pour chaque partition des éléments en sous-ensembles, tester s'il existe un ensemble d'entrée couvrant chaque sous-ensemble. Donc pour m = O ( log n / log log n ) le problème peut être résolu en temps polynomial. Cela ne répond pas tout à fait à votre question sur m = O ( log n ) . mO(m)mm=O(logn/loglogn)m=O(logn)
David Eppstein

Réponses:

11

Lorsque , vous pouvez utiliser la programmation dynamique pour trouver l'optimum en temps polynomial. Le tableau contient des cellules d'une valeur booléenne T , X pour chaque { 0 , ... , k } et X U , ce qui indique s'il y a ensembles qui couvrent les éléments de X .m=O(logn)T,X{0,,k}XUX

Lorsque , disonsmCm=O(n) , le problème reste NP-difficile. Étant donné une instance de SET-COVER, ajoutezmnouveaux élémentsx1,,xmet(2C - 1 m)2nouveaux ensembles, composés de sous-ensembles non vides des nouveaux éléments, y compris{x1,,xm}(lorsquemest assez grand,(2C - 1 m)2<2m). Augmentez égalementkmCnmx1,,xm(2C1m)2{x1,,xm}m(2C1m)2<2mkpar un. Les nouveaux sont m = 2 m et n = n + ( 2 C - 1 m ) 2( C - 1 m ) 2 .m,nm=2mn=n+(2C1m)2(C1m)2

Yuval Filmus
la source
Plus généralement, le cas est NP-dur, et le cas m = n o ( 1 ) n'est pas NP-dur en supposant ETH, car il existe un algorithme p o l y ( n , 2 m ) . m=nO(1)m=no(1)poly(n,2m)
Yuval Filmus
11

Le cas de est en n O ( c ) temps comme noté par Yuval, mais notez aussi pour k = O ( 1 ) que vous pouvez résoudre le problème en O ( n km ) temps (temps polynomial) en une recherche exhaustive. En supposant l'hypothèse de temps exponentiel fort (que CNF-SAT sur les formules avec N variables et clauses O ( N ) nécessite au moins 2 N - o ( N )m=clognnO(c)k=O(1)O(nkm)NO(N)2No(N)temps), ces deux bornes sont la "limite" de ce à quoi on peut s’attendre en temps polynomial, dans le sens suivant.

Dans mon article SODA'10 avec Mihai Patrascu, nous étudions le problème essentiellement isomorphe de trouver un ensemble dominant de taille dans un graphe arbitraire à n nœuds, montrant que si l'ensemble k- dominateur peut être résolu en n k - ε temps pour certains k 2 et ε > 0 , il existe alors un algorithme temporel 2 N ( 1 - ε / 2 ) p o l y ( M ) pour CNF-SAT sur N variables et Mknknkεk2ε>02N(1ε/2)poly(M)NM clauses.

En notant la relation entre les voisinages de sommets dans une instance d'ensemble dominante et les ensembles dans une instance de couverture d'ensemble, et en inspectant la réduction, vous constaterez que cette réduction montre également la résolution de -Set Cover avec n ensembles sur un univers de taille m dans n k - Le temps εf ( m ) implique un algorithme CNF-SAT pour les formules CNF avec M clauses et N variables s'exécutant dans 2 N ( 1 - ε / 2 )f ( M )knmnkεf(m)MN2N(1ε/2)f(M)temps. Pour réfuter l'ETH fort, il suffit de résoudre CNF-SAT dans le cas où . Par conséquent, un algorithme pour votre problème fonctionnant en n k - ε2 m / α ( m ) dans le temps pour une fonction non bornée α ( m ) produirait un nouvel algorithme SAT surprenant.M=O(N)nkε2m/α(m)α(m)

Ryan Williams
la source