Efficient algorithm for existence of permutation with differences sequence?

Question

This question is motivated by this post, Can you identify the sum of two permutations in polynomial time? , and my interest in computational properties of permutations.

A differences sequence $a_1, a_2, \ldots a_n$ of a permutation $\pi$ of numbers $1, 2, \ldots n+1$ is formed by finding the difference between every two adjacent numbers in the permutation $\pi$. In other words, $a_i= |\pi(i+1)-\pi(i)|$ for $1 \le i \le n$

For example, sequence $1, 1, 3$ is the differences sequence of permutation $2 3 4 1$. While, sequences $2, 2, 3$ and $ 3, 1, 2$ are not the differences sequence of any permutation of numbers $1, 2, 3, 4$.

Is there an efficient algorithm to determine whether a given sequence is the differences sequence for some permutation $\pi$, or is it NP-hard?

EDIT: We get computationally equivalent problem if we formulate the problem using circular permutations.

EDIT2: Cross posted on MathOverflow, How hard is reconstructing a permutation from its differences sequence?

EDIT3 Awarded the bounty to the proof sketch and I would accept the answer after getting the complete formal proof.

EDIT 4: Marzio's nice $NP$-completeness proof has been published in the Electronic Journal of Combinatorics.

Perhaps another trivial (but more sound?) comment is that if the $a_i$ are a permutation of $[1..n]$ (all values are distinct) then the problem is to verify that the sequence is a graceful labeling of the line of $n+1$ nodes which is solvable in polynomial time. — Marzio De Biasi, Jul 05 '13 at 15:04
@MarzioDeBiasi It think you share my passion for permutation problems. I hope that I came up with the simplest computationally interesting permutation problem :) — Mohammad Al-Turkistany, Jul 05 '13 at 15:43
:-) ... I would rather say that my comment comes directly from the hours I spent in vain on the graceful tree labeling problem ... however I've a fuzzy idea of a possible NP-complete reduction for your problem; if I succeed in formalizing it I'll post an answer. — Marzio De Biasi, Jul 05 '13 at 16:11
@MarzioDeBiasi I found this interesting comment by Shor stating that your problem, Job scheduling with a bottleneck problem, is equivalent to a special case of my problem. Here is Shor's comment: if $K=2N$, the problem is equivalent to finding a permutation of $1...2N$ so that $i_{2a−1}−i_{2a}=A_i$. This provides another proof of the $NP$-completeness of my problem. — Mohammad Al-Turkistany, Feb 22 '14 at 09:06

score 12 · Accepted Answer · edited Apr 13 '17 at 12:32

12

This is a sketch of a possible reduction to prove that it is NP-hard:

1) $a_i$ subsequences made of 1s (e.g. $...11111...$) (I call them 1SEQ) force a subsequence of increasing or decreasing numbers in the permutation;

2) if a value of $2$ is put in a long 1SEQ, it forces a hole (a missing number) and doesn't change the direction of the 1SEQ. For example: $1112112111$ forces two holes:

 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)

The holes must be filled in the rest of the permutation.

3) using a large enough 1SEQ, followed by a 1SEQ with some holes, followed by another large 1SEQ you can build a forced line;

4) putting together many forced lines you can build a permutation grid graph in which the nodes correspond to the missing numbers in the underlying forced permutation.

For example the sequence 1111111112111111111112111111111, forces the following 5x7 permutation grid graph:

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

(or its symmetric version). Note that if the grid has size $w \times w$ and $a,b$ are two missing numbers in the same vertical column then $|a-b|=kw$.

5) the Hamiltonian cycle on grid graphs problem is NP-complete; so given a grid graph $G$ (with holes) you can build the equivalent permutation grid graph;

6) from the last number of the permutation you can "jump" to a number corresponding to a hole (a node in $G$), and with a fixed sequence of moves you can simulate the traversal of $G$; this requires a rather complex gadget - the "selection gadget" - that must be created in another part of the permutation grid graph;

7) you can fill all the holes (i.e. complete the permutation) if and only if the original grid graph has an Hamiltonian cycle

EDIT: July, 27 2013

I tried to formally prove the NP completeness of the problem: I introduced a new problem (Crazy Frog problem) which is NPC. The Permutation Reconstruction from Differences problem is equivalent to the "1-D Crazy Frog problem without blocked cells" (which is also NPC).

For the details of the reduction see my question/answer on cstheory "Two Hamiltonian path variants" or download a draft of the proof "When a frog meets a permutation" :)) (I'm still checking/completing it)

edited Apr 13 '17 at 12:32

Community

1

answered Jul 11 '13 at 22:44

Marzio De Biasi

22,915
2
58
127

Nice, I am sure this will lead to a solution, the selection gadget is definitely realizable. – domotorp Jul 12 '13 at 07:45
@domotorp: I posted it (I'll post the select/sync part details in the next days); perhaps it contains an error that I don't see, however I bet $1 that that the whole reduction can be greatly simplified :-) – Marzio De Biasi Jul 12 '13 at 10:35
@MarzioDeBiasi Nice visualization. It seems that you are on the right track. Could you please post your answer on MathOverflow since there is considerable interest in the problem? – Mohammad Al-Turkistany Jul 12 '13 at 11:01
@MarzioDeBiasi Could you post your final answer (formal) before the bounty expires? – Mohammad Al-Turkistany Jul 14 '13 at 22:18
@MohammadAl-Turkistany: I have just returned from a trip, I'll try to formalize (and check with a CSP) the gadgets in the next days. – Marzio De Biasi Jul 20 '13 at 20:41
@MarzioDeBiasi Thanks a lot for your effort. – Mohammad Al-Turkistany Jul 20 '13 at 20:58
@MohammadAl-Turkistany: there is an immediate reduction from the "1-D Crazy Frog problem without blocked cells" (which I proved to be NPC) to your problem. See the answer to my question on the CFP and if you want download the related draft paper and give it a look if it can work. – Marzio De Biasi Jul 28 '13 at 23:39
@MarzioDeBiasi I skimmed your draft and I did not spot obvious gaps or errors. However, I had a difficultly of following the correspondence made by your reduction between the two certificates. Sorry for being late. Lately, my schedule is very hectic. – Mohammad Al-Turkistany Aug 03 '13 at 14:16
@MohammadAl-Turkistany: if you want, you can send me an email with the unclear points of the proof, I'll be glad to try to clarify them (and improve the proof itself). – Marzio De Biasi Aug 03 '13 at 22:23
@MarzioDeBiasi Thanks a lot for your generous offer. I will take advantage of it after Ramadan Holiday. – Mohammad Al-Turkistany Aug 04 '13 at 00:36

Efficient algorithm for existence of permutation with differences sequence?

1 Answers1

Linked