<p>This is a sketch of a possible reduction to prove that it is NP-hard:</p>

<p>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;</p>

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

<pre><code> 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)
</code></pre>

<p>The holes must be <em>filled</em> in the rest of the permutation.</p>

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

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

<p>For example the sequence 1111111112111111111112111111111, forces the following 5x7 permutation grid graph:</p>

<pre><code>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
</code></pre>

<p>(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$.</p>

<p>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;</p>

<p>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;</p>

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

<p><strong>EDIT: July, 27 2013</strong></p>

<p>I tried to formally prove the NP completeness of the problem: I introduced a new problem (<em>Crazy Frog problem</em>) 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).</p>

<p>For the details of the reduction see <a href="https://cstheory.stackexchange.com/questions/18440/two-hamiltonian-path-problem-variants">my question/answer  on cstheory
"Two Hamiltonian path variants"</a> or download a <a href="http://www.fractalmuse.org/vdisk/cstheory/crazyfrog.pdf" rel="nofollow noreferrer">draft of the proof "When a frog meets a permutation"</a> :)) (I'm still checking/completing it)</p>

CC BY-SA 3.0
2013-07-12T07:45:53.717Z
Nice, I am sure this will lead to a solution, the selection gadget is definitely realizable.
domotorp
CC BY-SA 3.0
2013-07-12T10:35:59.693Z
@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
CC BY-SA 3.0
2013-07-12T11:01:52.743Z
@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
CC BY-SA 3.0
2013-07-14T22:18:31.717Z
@MarzioDeBiasi Could you post your final answer (formal) before the bounty expires?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-07-20T20:41:48.730Z
@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
CC BY-SA 3.0
2013-07-20T20:58:47.803Z
@MarzioDeBiasi Thanks a lot for your effort.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-07-28T23:39:39.723Z
@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](http://cstheory.stackexchange.com/questions/18440/two-hamiltonian-path-problem-variants/18495#18495) and if you want download the related draft paper and give it a look if it can work.
Marzio De Biasi
CC BY-SA 3.0
2013-08-03T14:16:16.160Z
@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
CC BY-SA 3.0
2013-08-03T22:23:32.247Z
@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
CC BY-SA 3.0
2013-08-04T00:36:39.883Z
@MarzioDeBiasi Thanks a lot for your generous offer. I will take advantage of it after Ramadan Holiday.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-07-11T22:44:31.773Z
2013-07-29T09:28:52.333Z
2017-04-13T12:32:28.077Z
Marzio De Biasi
<p>This question is motivated by this post, <a href="https://cstheory.stackexchange.com/questions/18037/can-you-identify-the-sum-of-two-permutations-in-polynomial-time/18045#18045">Can you identify the sum of two permutations in polynomial time?</a> , and my interest in computational properties of permutations.</p>

<p>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$</p>

<p>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$. </p>

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

<p><strong>EDIT</strong>: We get computationally equivalent problem if we formulate the problem using circular permutations.</p>

<p><strong>EDIT2</strong>: Cross posted on MathOverflow, <a href="https://mathoverflow.net/questions/135968/how-hard-is-reconstructing-a-permutation-from-its-differences-sequence">How hard is reconstructing a permutation from its differences sequence?</a></p>

<p><strong>EDIT3</strong> Awarded the bounty to the proof sketch and I would accept the answer after getting the complete formal proof.</p>

<p><strong>EDIT 4</strong>: Marzio's nice $NP$-completeness proof has been published in <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p3" rel="nofollow noreferrer">the Electronic Journal of Combinatorics</a>.</p>

CC BY-SA 3.0
2013-07-05T15:04:25.013Z
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
CC BY-SA 3.0
2013-07-05T15:43:04.587Z
@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
CC BY-SA 3.0
2013-07-05T16:11:07.233Z
:-) ... 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
CC BY-SA 3.0
2014-02-22T09:06:30.607Z
@MarzioDeBiasi I found this interesting comment by Shor stating that your problem, [Job scheduling with a bottleneck problem](http://cs.stackexchange.com/questions/10869/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$](http://cs.stackexchange.com/q/12359/96). This provides another proof of the $NP$-completeness of my problem.
Mohammad Al-Turkistany
<cc.complexity-theory><co.combinatorics><np-hardness><permutations>
Efficient algorithm for existence of permutation with differences sequence?
Mohammad Al-Turkistany
# Efficient algorithm for existence of permutation with differences sequence?

(Asked by: username_0 on 2013-07-03)

This question is motivated by this post, [Can you identify the sum of two permutations in polynomial time?](https://cstheory.stackexchange.com/questions/18037/can-you-identify-the-sum-of-two-permutations-in-polynomial-time/18045#18045) , 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?](https://mathoverflow.net/questions/135968/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](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p3).

**Tags:** cc.complexity-theory, co.combinatorics, np-hardness, permutations

> **Comments:**
> **username_1**: 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.  
> **username_0**: @MarzioDeBiasi It think you share my passion for permutation problems. I hope that I came up with the simplest computationally interesting permutation problem :)  
> **username_1**: :-) ... 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.  
> **username_0**: @MarzioDeBiasi I found this interesting comment by Shor stating that your problem, [Job scheduling with a bottleneck problem](http://cs.stackexchange.com/questions/10869/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$](http://cs.stackexchange.com/q/12359/96). This provides another proof of the $NP$-completeness of my problem.  

---

## 1 answers

### Answer by username_1 on 2013-07-11. Score: 12 | Accepted answer

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)

> **Comments:**
> **username_2**: Nice, I am sure this will lead to a solution, the selection gadget is definitely realizable.  
> **username_1**: @username_2: 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 :-)  
> **username_0**: @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?  
> **username_0**: @MarzioDeBiasi Could you post your final answer (formal) before the bounty expires?  
> **username_1**: @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.  
> **username_0**: @MarzioDeBiasi Thanks a lot for your effort.  
> **username_1**: @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](http://cstheory.stackexchange.com/questions/18440/two-hamiltonian-path-problem-variants/18495#18495) and if you want download the related draft paper and give it a look if it can work.  
> **username_0**: @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.  
> **username_1**: @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).  
> **username_0**: @MarzioDeBiasi Thanks a lot for your generous offer. I will take advantage of it after Ramadan Holiday.  

---

