$NP$-completeness of recognizing the difference of two permutations

Question

Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two permutations. Unfortunately, I don't see a straightforward reduction from the permutation sum problem and it is useful to have the $NP$-completeness reduction for the permutation difference problem.

Permutation Difference:

INSTANCE: An array $A[1...n]$ of positive integers.

QUESTION: Do there exist two permutations $\pi$ and $\sigma$ of the positive integers $1,2, ... , n$ such that $|\pi(i) - \sigma(i)| = A[i]$ for $1 \le i \le n$ ?

What is the reduction for proving the $NP$-completeness of recognizing the difference of two permutations?

EDIT 10-9-2014: Shor's comment gives a reduction which proves $NP$-completeness when the elements of sequence $A$ are signed differences. However, I don't see an easy reduction to my problem where all elements of $A$ are the absolute values of differences.

UPDATE: The Permutation Difference problem seems to be $NP$-complete even if one of the two permutations is always the identity permutation. Hardness proof of this special case is very welcome. So, I am interested in $NP$-completeness of this restricted version:

Restricted Permutation Difference: INSTANCE: An array $A[1...n]$ of positive integers.

QUESTION: Does there exist a permutation $\pi$ of the positive integers $1,2, ... , n$ such that $|\pi(i) - i| = A[i]$ for $1 \le i \le n$ ?

Update 2: The restricted problem is efficiently decidable as shown by mjqxxxx's answer. The computational complexity of the original problem is not proven.

EDIT 9/6/16: I am interested in determining whether this simplification of Permutation Difference is NP-complete:

Restricted Permutation Difference:

INSTANCE: A multiset $A$ of positive integers.

QUESTION: Does there exist a permutation $\pi$ of the positive integers $1,2, ... , n$ such that $A= \{|\pi(i) - i| :1 \le i \le n\}$ ?

Answer 1

The restricted problem, where one of the permutations is the identity, is certainly in $\mathsf{P}$. Construct the bipartite graph where each vertex $i \in V_1=\{1,2,\ldots,n\}$ is connected to the element(s) $j \in V_2=\{1,2,\ldots,n\}$ such that $|i-j|=A[i]$. Then the desired permutation $\sigma$ exists if and only if the graph has a perfect matching (i.e., a matching with $n$ edges), which can be determined in polynomial time.

Answer 2

Here's a mildly interesting variation where the problem is easy: instead of a ground set of $\{1,2,3,\ldots,n\}$, allow any subset of $\{1,2,4,8,\ldots\}$. The goal is still to find a permutation $\pi$ so that $A = \{|\pi(2^k) - 2^k| : 2^k \in \Omega\}$ where $\Omega$ is the ground set. The main advantage here is that the new ground set forces each element of $A$ to be $2^{k_1}-2^{k_2}$ for some $k_1,k_2$, and if $k_1\ne k_2$, then $k_1$ and $k_2$ are determined by this difference. It follows that for each difference $|2^{k_1} - 2^{k_2}|$ in $A$, we may infer that $\pi(2^{k_1}) = 2^{k_2}$ or $\pi(2^{k_2}) = 2^{k_1}$ (or both).

Efficiently solving this simplified variation is then more or less routine. Begin by constructing the undirected bipartite multigraph $G = (L \sqcup R, E)$ where $L$ and $R$ are distinct copies of the ground set, and add edges $(2^{k_1},2^{k_2})$ and $(2^{k_2},2^{k_1})$ whenever $|2^{k_1} - 2^{k_2}|$ appears in $A$ with $k_1 \ne k_2$. I claim that the following are equivalent:

1. There is a permutation $\pi$ with differences $A$
2. Every vertex in $G$ has degree 0 or 2

I won't actually prove this because of time, but it's not too bad to work out on one's own. That $1 \implies 2$ is straightforward. That $2 \implies 1$ is a bit more arduous, but it's not too bad when you reason with the automorphism of $G$ which sends each vertex in $L$ to its copy in $R$ (and vice-versa). The proof I have in mind directs the edges in $G$ so that all edges in a cycle go ``the same way around the cycle'' (each nonisolated vertex has in-degree = out-degree = 1), and so that the preceding automorphism of $G$ remains an automorphism of the directed version. $\pi$ is then chosen according to the edges that go from $L$ to $R$.

You can phrase the above algorithm as a perfect matching question, and I imagine there are other reductions to 2-SAT. I don't see how to extend these approaches to the original problem though.