Bijections monótonos entre listas de intervalos

10

Eu tenho o seguinte problema:

Entrada: dois conjuntos de intervalos e (todos os pontos de extremidade são inteiros). Consulta: existe uma bijeção monótona ?T f : S TST
f:ST

O bijeç~ao é monótona wrt da ordem inclusão conjunto em e . T X Y S , F ( X ) f ( Y )ST

XYS, f(X)f(Y)

[Não estou exigindo a condição inversa aqui. Atualização: se a condição inversa fosse necessária, ou seja, , isso seria em PTIME porque equivale a teste de isomorfismo da inclusão correspondente posets (que têm dimensão de ordem 2 por construção), que está em PTIME por Möhring, Classes computacionalmente tratáveis ​​de conjuntos ordenados , Teorema 5.10, p. 61X,Y,XYf(X)f(Y) ]

O problema está em : podemos verificar com eficiência se um dado é uma bijeção monótona. fNPf

Existe um algoritmo de tempo polinomial para esse problema? Ou é -hard?NP

A questão pode ser declarada de maneira mais geral como a existência de uma bijeção monótona entre dois posets dados da dimensão de ordem 2.

Usando uma redução inspirada nas respostas a esta pergunta , sei que o problema é -hard quando as dimensões não são restritas. No entanto, não está claro se a redução também funcionaria quando as dimensões forem restritas.NP

Também estou interessado em saber sobre tratabilidade quando a dimensão é apenas delimitada por alguma constante arbitrária (não apenas 2).

a3nm
fonte
Existem contra-exemplos para essa abordagem gananciosa: classifique os intervalos de acordo com o comprimento decrescente; construa uma árvore nós desta maneira: se , adicione aresta , se houver vários intervalos com o mesmo comprimento comdepois, escolha a extremidade esquerda e adicione a aresta . Adicione uma raiz vinculada aos nós sem arestas recebidas. Construa uma árvore semelhante para e verifique se as duas são isomórficas. S I1,I2,...,Inn+1IiIj(IjIi)IiIj1,...,Ijm|Ij1|=|Ij2|=...=|Ijm|(IjkIi)T
Marzio De Biasi
2
Um intervalo pode ser incluído em vários intervalos incomparáveis, por exemplo, [2, 3] está incluído em [1, 3] e [2, 4], então acho que a construção de sua árvore não produzirá uma árvore, mas um gráfico acíclico direcionado. Verificar se dois DAGs são isomórficos (ou melhor, incorporáveis ​​no sentido em que estou perguntando) é difícil para o NP em geral, acho.
A3nm
Você está certo, a abordagem acima não está correta!
Marzio De Biasi
De acordo com a resposta de De Biasi, o problema é GI-completo quando . No entanto, sua postagem afirma que está em PTIME. Qual deles está correto? X,Y,XYf(X)f(Y)
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: cf a discussão nos comentários sobre a resposta de Marzio
a3nm

Respostas:

8

Aqui está uma tentativa de provar que o problema sem a condição reversa é NP-difícil.

A idéia básica é que intervalos separados em como este:S

 [S]  +-a-+ +-b-+
      +---c-----+  c<a, c<b (here < is interval inclusion)

pode ter um mapeamento válido para uma " pirâmide " em :T

 [T]  +-x-+      f(a)=x, f(b)=y, f(c)=z
      +-y---+    
      +-z-----+  z<x, z<y OK

A redução é da 3-Partição Unária (que é o NPC). Dado números inteiros e um número inteiro , existe uma partição de A nos conjuntos de modo que todo tenha exatamente 3 elementos e a soma deles é ?3mA={a1,a2,...,a3m}BmA1,...,AmAiB

Suponha quemax=ai+3m

Construímos adicionando intervalos base de de comprimento (linhas vermelhas na figura); no topo de cada intervalo base, adicionamos uma pirâmide de marcadores de intervalos de comprimento crescente (linhas verdes na figura). Para basear o intervalo , também adicionamos intervalos unitários separados de comprimento 1 (linhas pretas na figura). Finalmente, adicionamos um longo intervalo para cobrir todo o (linha azul na figura).3 m B I i 3 * m a x m um X B I i um i G B I iS3m BIi3maxmaxBIiaiLBIi

TLm GjGjB

Suponha que exista uma bijeção entre S e T que preserve a inclusão do intervalo (em uma direção de S para T).

maxBIj1,BIj2,BIj3SGjBIjkGj

De maneira semelhante, pode-se provar que, se existir uma bijeção, o problema unário de 3 partições original terá uma solução.

insira a descrição da imagem aquim=2,A={3,3,2,2,2,2},B=7

Nota: como observado nos comentários, os intervalos azuis L em S e T não são essenciais para a redução.

IiIj(IjIi)

Marzio De Biasi
fonte
Sim, parece que isso está correto, muito obrigado! (Apenas uma observação: acho que os intervalos azuis não são necessários para que a redução funcione.) Aceitarei em breve, a menos que encontre um motivo para duvidar que essa redução funcione.
a3nm
@ a3nm: sim, mas descobri depois de desenhar a figura :-). Ainda não tenho 100% de certeza de que não há erros ocultos na redução (além disso, é a segunda vez em duas semanas que encontro uma prova completa de NP que usa três partições unárias ... muito estranho :-)
Marzio De Biasi 17/10
Não, parece certo: claramente uma solução para 3 partições produz uma solução para o problema do intervalo. Agora, passando do problema do intervalo para a partição 3: necessariamente um mapeamento de intervalo mapeia os intervalos vermelhos para intervalos vermelhos (por causa das pirâmides dos marcadores); mesmo número de intervalos vermelhos, portanto o intervalo é vermelho se a imagem do mapeamento for. Os marcadores são mapeados para o intervalo vermelho certo (porque, caso contrário, é um descendente e uma minoria). Agora, se vermelho é mapeado para vermelho e os marcadores são mapeados conforme o esperado, os números precisam corresponder, para que tenhamos uma partição correta. Eu acho que faz sentido!
a3nm
@ a3nm: vi que você aceitou a resposta; você acha que o resultado é interessante o suficiente para escrever um trabalho conjunto?
Marzio De Biasi
Tf