Dureza de un subcase de Set Cover

10

¿Qué tan difícil es el problema de Set Cover si el número de elementos está limitado por alguna función (por ejemplo, logn ) donde n es el tamaño de la instancia del problema. Formalmente,

Let y F = { s 1 , , S n } donde S iU y m = O ( log n ) . ¿Qué tan difícil es decidir el siguiente problema?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}.

¿Qué pasa si m=O(n) ?

Cualquier resultado basado en conjeturas bien conocidas (por ejemplo, Juegos únicos, ETH) es bueno.

Edición 1: Una motivación para este problema es descubrir cuándo el problema se vuelve difícil a medida que aumenta . Claramente, el problema está en P si m = O ( 1 ) y NP-hard si m = O ( n )mm=O(1)m=O(n) . ¿Cuál es el umbral para la dureza NP del problema?

Edición 2: existe un algoritmo trivial para decidirlo en el tiempo (que enumera todos los subconjuntos de tamaño m de F ). Por lo tanto, el problema no es NP-hard si m = O ( log n ) ya que ETH implica que no hay algoritmo en el tiempo O ( 2 n o ( 1 ) ) para ningún problema NP-hard (donde n es el tamaño del Problema NP-duro).O(nm)mFm=O(logn)O(2no(1))n

usuario1297
fuente
2
Existe un mejor algoritmo para decidir el problema en el tiempo (más precisamente el número de Bell para m ): para cada partición de los elementos en subconjuntos, pruebe si existe un conjunto de entrada que cubra cada subconjunto. Entonces, para m = O ( log n / log log n ), el problema se puede resolver en tiempo polinómico. Sin embargo, esto no responde a su pregunta sobre m = O ( log n ) . mO(m)mm=O(logn/loglogn)m=O(logn)
David Eppstein

Respuestas:

11

Cuando , puede utilizar la programación dinámica para encontrar el tiempo óptimo en el polinomio. La tabla contiene celdas con valores booleanos T , X para cada { 0 , ... , k } y X U , lo que indica si hay conjuntos que cubren los elementos en Xm=O(logn)T,X{0,,k}XUX .

Cuando , diga m C m=O(n) , el problema sigue siendo NP-duro. Dada una instancia de SET-COVER, addmnuevos elementosx1,...,xmy(2C - 1 m)2nuevos conjuntos, que consta de subconjuntos no vacíos de los nuevos elementos, incluyendo{x1,...,xm}(cuandomes lo suficientemente grande,(2C - 1 m)2<2m). También aumentakmCnmx1,,xm(2C1m)2{x1,,xm}m(2C1m)2<2mk por uno. Los nuevos son m m,n y n ' = n + ( 2 C - 1 m ) 2( C - 1 mm=2m .n=n+(2C1m)2(C1m)2

Yuval Filmus
fuente
Más generalmente, el caso es NP-hard, y el caso m = n o ( 1 ) no NP-hard suponiendo ETH, ya que existe un algoritmo p o l y ( n , 2 m ) . m=nO(1)m=no(1)poly(n,2m)
Yuval Filmus
11

El caso de está en n O ( c ) tiempo como lo señaló Yuval, pero también tenga en cuenta que para k = O ( 1 ) puede resolver el problema en O ( n km ) tiempo (tiempo polinómico) por búsqueda exhaustiva. Suponiendo la hipótesis del tiempo exponencial fuerte (que CNF-SAT en fórmulas con N variables y cláusulas O ( N ) requiere al menos 2 N - o ( N )m=clognnO(c)k=O(1)O(nkm)NO(N)2No(N)tiempo), estos dos límites de tiempo son el "límite" de lo que podemos esperar en el tiempo polinómico, en el siguiente sentido.

En mi artículo de SODA'10 con Mihai Patrascu , estudiamos el problema esencialmente isomórfico de encontrar un conjunto dominante de tamaño en un gráfico arbitrario de n- nodos, mostrando que si el conjunto dominante de k se puede resolver en n k - ε tiempo por algún k 2 y ε > 0 , entonces hay un algoritmo de tiempo 2 N ( 1 - ε / 2 ) p o l y ( M ) para CNF-SAT en N variables y Mknknkεk2ε>02N(1ε/2)poly(M)NM cláusulas

Observando la relación entre vecindarios de vértices en una instancia de conjunto dominante y conjuntos en una instancia de cobertura de conjunto, e inspeccionando la reducción, encontrará que esta reducción también muestra la resolución de -Set Cover con n conjuntos sobre un universo de tamaño m en n k - El tiempo εf ( m ) implica un algoritmo CNF-SAT para fórmulas CNF con cláusulas M y N variables que se ejecutan en 2 N ( 1 - ε / 2 )f ( Mknmnkεf(m)MN2N(1ε/2)f(M)hora. A los efectos de refutar el Strong ETH, es suficiente resolver CNF-SAT en el caso de que . Por lo tanto, un algoritmo para su problema que se ejecuta en n k - ε2 m / α ( m ) para alguna función ilimitada α ( m ) produciría un nuevo algoritmo SAT sorprendente.M=O(N)nkε2m/α(m)α(m)

Ryan Williams
fuente