Eu acho que esse problema é NP-difícil. Eu tento esboçar uma redução do MinSAT. No problema do MinSAT, recebemos um CNF e nosso objetivo é minimizar o número de cláusulas satisfeitas. Esse problema é difícil para o NP, veja, por exemplo, http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec
Divida os vértices em dois grupos - alguns representarão literais, as outras cláusulas, então que é o número de variáveis da CNF (geralmente denotado por ) é o número de cláusulas. Direcione uma aresta de cada literal-vértice para a cláusula-vértice onde ela ocorre. Definir para um literal-vértice que representa como (onde é um parâmetro arbitrária), então ou e ou e . Para cada vertente de cláusula, deixev n c S x i { i , i + v + k } k f ( x i ) = i f ( ˉ x i ) = i + v + k f ( ˉ x i ) = i f ( x i ) = i + v + k Sn=2v+cvncSxi{i,i+v+k}kf(xi)=if(x¯i)=i+v+kf(x¯i)=if(xi)=i+v+kS={v+1,…,v+k,2v+k+1,…,n}, então dos vértices da cláusula é `` pequeno ''.k
Agora, a CNF tem uma atribuição em que pelo menos cláusulas são falsas se e somente se o seu problema puder ser resolvido na instância acima. O problema do MinSAT é exatamente para testar se uma fórmula CNF tem uma atribuição que torna pelo menos cláusulas falsas, portanto, isso mostra que seu problema é difícil para o NP.kφk
Para ajudar você a entender essa redução, eis a intuição: rótulos pequenos ( ) correspondem ao valor verdadeiro Falso e rótulos grandes ( ) correspondem para True. As restrições para vértices literais garantem que cada seja Verdadeiro ou Falso e que tenha o valor de verdade oposto. As arestas garantem que, se algum literal for True, todos os vértices de cláusula que o contêm também sejam True. (Por outro lado, se todos os literais em uma cláusula forem atribuídos False, essa estrutura do gráfico permitirá que a cláusula-vértice seja atribuída como False ou True.) Por fim, a escolha de garante que dos vértices da cláusula sejam atribuídos False e1,2,…,v+kv+k+1,…,2v+kxixi¯¯¯¯¯kkc−kdeles são atribuídos como True. Portanto, se houver um tipo topológico válido desse gráfico, haverá uma atribuição às variáveis que tornarão pelo menos das cláusulas de falsas (todos os vértices de cláusula que foram atribuídos False, além de possivelmente alguns dos aqueles que foram atribuídos como True). Por outro lado, se houver uma atribuição para as variáveis que torna pelo menos das cláusulas de falsas, existe um tipo topológico válido deste gráfico (preenchemos os rótulos dos vértices literais da maneira óbvia; e para cada cláusula dekφkφφisso é verdade, atribuímos à sua cláusula-vértice correspondente um rótulo que corresponde a True; os outros vértices de cláusula podem receber rótulos correspondentes a um valor de verdade arbitrário).
Observe que, se você relaxar o problema, permitindo que seja arbitrário (não necessariamente bijetivo), ele se tornará polinomial. O algoritmo procede de maneira semelhante à classificação topológica: você numera os vértices um por um, mantendo o conjunto U de vértices não numerados cujos vizinhos vizinhos foram numerados. Sempre que possível, você escolhe um vértice x ∈ U e o numera com o menor elemento de S ( x ) maior que os números de seus vizinhos vizinhos. Não é difícil ver que uma instância ( G , S ) tem uma solução se o algoritmo anterior é executado em ( G ,f U x∈U S(x) (G,S) termina com todos os vértices numerados.(G,S)
fonte
Uma observação trivial é que se para todos os x , então esse problema é solucionável em tempo polinomial, por redução para 2SAT.|S(x)|≤2 x
Aqui está como. Introduza uma variável para cada vértice x e cada i tal que i ∈ S ( x ) . Para cada par x , y de vértices, se há um caminho de x para y , obtemos algumas restrições: se i ∈ S ( x ) , j ∈ S ( y ) , e i > j , então nós começamos a restrição ¬ v x , ivx,i x i i∈S(x) x,y x y i∈S(x) j∈S(y) i>j . Bijectivity nos dá um outro conjunto de restrições: para cada par x , y de vértices com x ≠ y , se i ∈ S ( x ) e i ∈ S ( y ) , adicionamos ¬ v x , i ∨ ¬ v y , i . Por fim, o requisito de que cada vértice deva receber um rótulo fornece um outro conjunto de restrições: para cada x , se S (¬vx,i∨¬vy,j x,y x≠y i∈S(x) i∈S(y) ¬vx,i∨¬vy,i x , obtemos a restrição v x , i ∨ v x , j . (Observe que apenas o último conjunto de restrições explora a promessa de que | S ( x ) | ≤ 2 para cada x .)S(x)={i,j} vx,i∨vx,j |S(x)|≤2 x
Sei que essa observação não irá ajudá-lo em sua situação particular. Me desculpe por isso.
fonte