Quão difícil é o problema Set Cover se o número de elementos estiver delimitado por alguma função (por exemplo, ) em que é o tamanho da instância do problema. Formalmente,n
Deixe e que e . Quão difícil é decidir o seguinte problemaF = { S 1 , ⋯ , S n } S i ⊆ U m = O ( log n )
E se ?
Qualquer resultado baseado em conjecturas conhecidas (por exemplo, Unique Games, ETH) é bom.
Edit 1: Uma motivação para esse problema é descobrir quando o problema fica difícil à medida que aumenta. Claramente, o problema está em P se e NP-rígido se . Qual é o limite para a dureza NP do problema?m = O ( 1 ) m = O ( n )
Edit 2: Existe um algoritmo trivial para decidi-lo no tempo (que enumera todos os subconjuntos de tamanho de ). Portanto, o problema não é NP-difícil se pois ETH implica que não há algoritmo no tempo para qualquer NP-rígido problem (onde é o tamanho do problema NP-hard).m F m = O ( log n ) O ( 2 n o ( 1 ) ) n
fonte
Respostas:
Quando , você pode usar a programação dinâmica para encontrar o melhor em tempo polinomial. A tabela contém células com valor booleano para cada e , indicando se existem conjuntos de que cobrem o elementos em .m = O ( logn ) ℓ ∈ { 0 , ... , k } X ⊆ U ℓ XTℓ , X l ∈ { 0 , ... , k } X⊆ U ℓ X
Quando , digamos , o problema permanece NP-difícil. Dada uma instância de SET-COVER, adicione novos elementos em≤C √m = O ( n--√) mx1,…,xm(2C - 1 m)2novos conjuntos, consistindo em subconjuntos não vazios dos novos elementos, incluindo{x1,…,xm}(quandomfor grande o suficiente,(2C - 1 m)2<2m). Aumente tambémkem um. Os novosm,nsãom′=2m ≤ Cn--√ m x1 1, … , Xm ( 2 C- 1m )2 { x1 1, … , Xm} m ( 2 C- 1m )2< 2m k m,n e n ′ = n + ( 2 C - 1 m ) 2 ≥ ( C - 1 m ′ ) 2 .m′=2m n′=n+(2C−1m)2≥(C−1m′)2
fonte
O caso de é em n O ( c ) tempo, como observado por Yuval, mas também observe que k = O ( 1 ) você pode resolver o problema em tempo de O ( n k ⋅ m ) (tempo polinomial) por Pesquisa exaustiva. Supondo a hipótese de tempo exponencial forte (que CNF-SAT em fórmulas com N variáveis e cláusulas O ( N ) requer pelo menos 2 N - o ( N )m=clogn nO(c) k=O(1) O(nk⋅m) N O(N) 2N−o(N) tempo), esses dois limites de tempo são o "limite" do que podemos esperar no tempo polinomial, no sentido a seguir.
Na minha papel SODA'10 com Mihai Patrascu nós estudamos o problema essencialmente isomórfica de encontrar um conjunto dominante de tamanho em uma arbitrária n gráfico -node, mostrando que, se k -dominating conjunto pode ser resolvido em n k - ε tempo para alguns k ≥ 2 e ε > 0 , então existe uma 2 N ( 1 - ε / 2 ) p o l y ( H ) algoritmo de tempo para CNF-SAT em N variáveis e Mk n k nk−ε k≥2 ε>0 2N(1−ε/2)poly(M) N M cláusulas.
Observando a relação entre vizinhanças de vértices em uma instância de conjunto dominante e conjuntos em uma instância de cobertura de conjunto e inspecionando a redução, você verá que essa redução também mostra a solução de -Set Cover com n conjuntos em um universo de tamanho m em n k - ε ⋅ f ( m ) time implica um algoritmo CNF-SAT para fórmulas CNF com cláusulas M e N variáveis rodando em 2 N ( 1 - ε / 2 ) ⋅ f ( M )k n m nk−ε⋅f(m) M N 2N(1−ε/2)⋅f(M) Tempo. Para fins de refutar o Strong ETH, basta resolver o CNF-SAT no caso em que . Portanto, um algoritmo para o seu problema em execução em n k - ε ⋅ 2 m / α ( m ) para uma função ilimitada α ( m ) produziria um novo algoritmo SAT surpreendente.M=O(N) nk−ε⋅2m/α(m) α(m)
fonte