Dureza de uma subcaixa de Set Cover

10

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,nlognn

Deixe e que e . Quão difícil é decidir o seguinte problemaF = { 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}.

E se ?m=O(n)

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 )mm=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 ) ) nO(nm)mFm=O(logn)O(2no(1))n

user1297
fonte
2
Existe um algoritmo melhor para decidir o problema no tempo (mais precisamente o número de Bell para m ): para cada partição dos elementos em subconjuntos, teste se existe um conjunto de entradas que cubra cada subconjunto. Portanto, para m = O ( log n / log log n ), o problema pode ser resolvido em tempo polinomial. Isso ainda não responde à sua pergunta sobre . mO(m)mm=O(logn/loglogn)m=O(logn)
David Eppstein

Respostas:

11

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 UXT,X{0,,k}XUX

Quando , digamos , o problema permanece NP-difícil. Dada uma instância de SET-COVER, adicione novos elementos emCm=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=2mCnmx1,,xm(2C1m)2{x1,,xm}m(2C1m)2<2mkm,n e n = n + ( 2 C - 1 m ) 2( C - 1 m ) 2 .m=2mn=n+(2C1m)2(C1m)2

Yuval Filmus
fonte
De um modo mais geral, o caso é NP-difícil, e o caso m = n O ( 1 ) não é NP-difícil assumindo ETH, uma vez que existe um algoritmo p o l y ( n , 2 m ) . m=nO(1)m=no(1)poly(n,2m)
Yuval Filmus
11

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 km ) (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=clognnO(c)k=O(1)O(nkm)NO(N)2No(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 Mknknkεk2ε>02N(1ε/2)poly(M)NM 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 )knmnkεf(m)MN2N(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)

Ryan Williams
fonte