Algoritmo eficiente para existência de permutação com sequência de diferenças?

12

Esta questão é motivada por este post. Você consegue identificar a soma de duas permutações no tempo polinomial? , e meu interesse em propriedades computacionais de permutações.

Uma sequência de diferenças de uma permutação dos números é formada pela descoberta da diferença entre cada dois números adjacentes na permutação . Em outras palavras,para π 1 , 2 , n + 1 π a i = | π ( i + 1 ) - π ( i ) | 1 i na1,a2,anπ1,2,n+1πai=|π(i+1)π(i)|1in

Por exemplo, a sequência é a sequência de diferenças da permutação . Embora as sequências e não sejam a sequência de diferenças de qualquer permutação dos números .2 3 4 1 2 , 2 , 3 3 , 1 , 2 1 , 2 , 3 , 41,1,323412,2,33,1,21,2,3,4

Existe um algoritmo eficiente para determinar se uma determinada sequência é a sequência de diferenças para alguma permutação ou é NP-difícil?π

EDIT : Obteremos problema computacionalmente equivalente se formularmos o problema usando permutações circulares.

EDIT2 : Cross postado no MathOverflow, Quão difícil é reconstruir uma permutação a partir de sua sequência de diferenças?

EDIT3 Concedeu a recompensa ao esboço da prova e eu aceitaria a resposta depois de obter a prova formal completa.

EDIT 4 : A boa prova de completude de Marzio foi publicada no Electronic Journal of Combinatorics .NP

Mohammad Al-Turkistany
fonte
1
Talvez outro comentário trivial (mas mais sólido?) que, se o é uma permutação de (todos os valores são distintos), o problema é verificar se a sequência é uma rotulação graciosa da linha de nós que são solucionáveis ​​em tempo polinomial. [ 1 .. n ] n + 1ai[1..n]n+1
Marzio De Biasi
2
@MarzioDeBiasi Acho que você compartilha minha paixão por problemas de permutação. Espero que eu vim com o mais simples problema permutação computacionalmente interessante :)
Mohammad Al-Turkistany
2
:-) ... Prefiro dizer que meu comentário vem diretamente das horas que passei em vão sobre o problema de rotulagem de árvores graciosas ... no entanto, tenho uma idéia difusa de uma possível redução de NP-completa para o seu problema; se eu conseguir formalizá-lo, postarei uma resposta.
Marzio De Biasi
@MarzioDeBiasi Achei esse comentário interessante de Shor afirmando que seu problema, agendamento de tarefas com um problema de gargalo , é equivalente a um caso especial do meu problema. Aqui está o comentário de Shor: se , o problema é equivalente a encontrar uma permutação de modo que1 ... 2 N i 2 a - 1 - i 2 a = A iK=2N1...2Ni2a1i2a=Ai . Isso fornece outra prova da complexidade do meu problema no . NP
Mohammad Al-Turkistany

Respostas:

10

Este é um esboço de uma possível redução para provar que é NP-difícil:

1) subsequências feitas de 1s (por exemplo ) (eu as chamo de 1SEQ) forçam uma subsequência de números crescentes ou decrescentes na permutação; . . .11111 . . .ai...11111...

2) se um valor for colocado em um 1SEQ longo, ele força um furo (um número ausente) e não altera a direção do 1SEQ. Por exemplo: força dois furos:111211211121112112111

 a_i seq.:     1 1 1  2  1 1  2   1  1  1  forces
 permutation: 1 2 3 4 _ 6 7 8 _ 10 11 12 13 (or its decreasing equivalent)
 (from 4 you cannot go back to 2,
 from 8 you cannot go back to 6)

Os furos devem ser preenchidos no restante da permutação.

3) usando um 1SEQ grande o suficiente, seguido por um 1SEQ com alguns orifícios, seguido por outro 1SEQ grande, você pode construir uma linha forçada ;

4) reunindo muitas linhas forçadas, é possível criar um gráfico de grade de permutação no qual os nós correspondam aos números ausentes na permutação forçada subjacente.

Por exemplo, a sequência 1111111112111111111112111111111, força o seguinte gráfico de grade de permutação 5x7:

29 30 31 32 33 34 35
22 23 24    26 27 28
15 16 17 18 19 20 21
 8  9 10    12 13 14   
 1  2  3  4  5  6  7

(ou sua versão simétrica). Observe que se a grade tiver tamanho e houver dois números ausentes na mesma coluna vertical, .a , b | a - b | = k ww×wa,b|ab|=kw

5) o problema do ciclo hamiltoniano em gráficos de grade é NP-completo; então, dado um gráfico de grade (com furos), você pode criar o gráfico de grade de permutação equivalente;G

6) do último número da permutação, você pode "pular" para um número correspondente a um buraco (um nó em ) e, com uma sequência fixa de movimentos, você pode simular a travessia de ; isso requer um gadget bastante complexo - o "gadget de seleção" - que deve ser criado em outra parte do gráfico da grade de permutação;GGG

7) você pode preencher todos os furos (isto é, completar a permutação) se e somente se o gráfico original tiver um ciclo hamiltoniano

EDIT: 27 de julho de 2013

Tentei provar formalmente a integridade do problema em NP: introduzi um novo problema (problema do Crazy Frog ), que é o NPC. O problema de reconstrução da permutação a partir das diferenças é equivalente ao "problema 1-D Crazy Frog sem células bloqueadas" (que também é NPC).

Para obter detalhes da redução, consulte minha pergunta / resposta na história "Duas variantes de caminho hamiltoniano" ou faça o download do rascunho da prova "Quando um sapo encontra uma permutação" :)) (ainda estou verificando / completando)

Marzio De Biasi
fonte
Bom, tenho certeza de que isso levará a uma solução, o gadget de seleção é definitivamente realizável.
111313 domotorp
@domotorp: eu publiquei (vou postar os detalhes da parte de seleção / sincronização nos próximos dias); talvez ele contém um erro que eu não vejo, no entanto eu aposto $ 1 que que toda a redução pode ser muito simplificada :-)
Marzio De Biasi
@MarzioDeBiasi Nice visualization. Parece que você está no caminho certo. Você poderia postar sua resposta no MathOverflow, pois há um interesse considerável no problema?
Mohammad Al-Turkistany
@MarzioDeBiasi Você poderia postar sua resposta final (formal) antes que a recompensa expire?
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Acabei de voltar de uma viagem, vou tentar formalizar (e verificar com um CSP) os gadgets nos próximos dias.
Marzio De Biasi