¿Qué tan difícil es el problema de Set Cover si el número de elementos está limitado por alguna función (por ejemplo, ) donde es el tamaño de la instancia del problema. Formalmente,
Let y F = { s 1 , ⋯ , S n } donde S i ⊆ U y m = O ( log n ) . ¿Qué tan difícil es decidir el siguiente problema?
¿Qué pasa si ?
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 ) . ¿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).
fuente
Respuestas:
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} X⊆U ℓ X .
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 aumentakm≤Cn−−√ m x1,…,xm (2C−1m)2 {x1,…,xm} m (2C−1m)2<2m k por uno. Los nuevos son m ′m,n y n ' = n + ( 2 C - 1 m ) 2 ≥ ( C - 1 mm′=2m .n′=n+(2C−1m)2≥(C−1m′)2
fuente
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 k ⋅ m ) 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=clogn nO(c) k=O(1) O(nk⋅m) N O(N) 2N−o(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 Mk n k nk−ε k≥2 ε>0 2N(1−ε/2)poly(M) N M 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 ( Mk n m nk−ε⋅f(m) M N 2N(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)
fuente