Complexidade de classificação topológica com posições restritas

15

Recebi como entrada um DAG de vértices em que cada vértice é adicionalmente rotulado com algum .n x S ( x ) { 1 , , n }GnxS(x){1,,n}

Um tipo topológico de é uma bijeção dos vértices de para modo que, para todo , , se houver um caminho de para em então f (x) \ leq f (y) . Desejo decidir se existe um tipo topológico de G tal que para todos x , f (x) \ em S (x) .f G { 1 , , n } x y x y G f ( x ) f ( y ) G x f ( x ) S ( x )GfG{1,,n}xyxyGf(x)f(y)Gxf(x)S(x)

Qual é a complexidade desse problema de decisão?

[Notas: Claramente, isso está em NP. Se você observar o gráfico de pares de vértices / posições permitidos, com arestas não direcionadas entre pares que conflitam porque violam a ordem, você obtém um gráfico de cliques disjuntos onde deseja escolher no máximo um par por clique, no máximo um par por posição e no máximo um par por vértice - parece relacionado à correspondência tridimensional, mas não vejo se ainda é difícil com a estrutura adicional desse problema específico.]

a3nm
fonte

Respostas:

9

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¯kkckdeles 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).

domotorp
fonte
Obrigado pela sua resposta! Estou tentando entender seu esboço. Você se importaria de explicar o que é ? k
a3nm
1
@ a3nm: k é um parâmetro fornecido para a entrada MinSAT.
domotorp 19/09/13
1
@Marzio: SAT não é equivalente ao MinSAT com , como no último problema, exigiríamos que todas as cláusulas fossem falsas. Seu ϕ não possui uma atribuição falsa de todas as cláusulas. Claro que isso não prova meu redução é correta ...k=|c|ϕ
domotorp
Esta é uma redução maravilhosa! @ a3nm, sugeri uma edição da resposta para explicar a redução elegante da domotorp com mais detalhes; se for aprovado, espero que ajude você a entender as idéias mais claramente.
DW
@domotorp: você está certo, eu perdi completamente o que é MinSAT. Nice redução !!!
Marzio De Biasi
2

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 ,fUxUS(x)(G,S) termina com todos os vértices numerados.(G,S)

Super0
fonte
Na verdade, esse relaxamento significa que uma heurística gananciosa funciona, e isso é mesmo no caso em que não é o número de vértices, mas um valor arbitrário. Concordamos que, no último caso, onde injetividade e supressividade não são mais equivalentes, você precisaria relaxar os dois (e não apenas um) para que a heurística gananciosa funcione? n
A3nm 19/09/2013
2

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)|2x

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,ixiiS(x)x,yxyiS(x)jS(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,jx,yxyiS(x)iS(y)¬vx,i¬vy,ix , obtemos a restrição v x , iv 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,ivx,j|S(x)|2x

Sei que essa observação não irá ajudá-lo em sua situação particular. Me desculpe por isso.

DW
fonte