21
$\begingroup$

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\}$ ?

$\endgroup$
  • $\begingroup$ Why not ask Peter directly? @Peter $\endgroup$ – caozhu Feb 21 '14 at 3:28
  • $\begingroup$ Do you mean by Email? I will do that. $\endgroup$ – Mohammad Al-Turkistany Feb 21 '14 at 3:32
  • $\begingroup$ I may be missing something but can't this problem be represented as a 2-SAT and thus be solved in polytime? We can assume WLOG that one of the permutations is the identity (I'm assuming here that A[i] is calculated cyclically; should that matter much?), and then we can represent the second one by a matrix $x[i,j]$. Being a permutation matrix is a conjunction of the clauses of two variables stating that no two ones lie in a row or in a column; and then saying that the difference is in locations of pi(i) from i is A[i] is the OR of the two possible places it can be in. $\endgroup$ – Noam Feb 23 '14 at 19:16
  • $\begingroup$ @Noam Thank you for your comment. Interesting idea. I did not think of it. However, It is not obvious to me whether it will lead to polynomial time algorithm especially that we are given only the absolute value of the differences. $\endgroup$ – Mohammad Al-Turkistany Feb 23 '14 at 19:49
  • 1
    $\begingroup$ Yes, it seems that the difference between counting the gap cyclically or in absolute value can matter. $\endgroup$ – Noam Feb 23 '14 at 20:45
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I may be missing something, but any perfect matching will not work. You must prove the existence of restricted perfect matching. Consider an integer $k$ which occurs twice in input array $A$. The perfect matching that corresponds to the permutation must have two edges with absolute difference $k$. Your algorithm does NOT prove the existence of such restricted matching. This is what make the problem hard and possibly NP-complete. $\endgroup$ – Mohammad Al-Turkistany Dec 11 '14 at 18:49
  • 2
    $\begingroup$ @MohammadAl-Turkistany: I think that if $A[i] = A[j] = k$ then $u_i, u_j \in V_1$ are linked to nodes $v_{i+A[i]},v_{i-A[i]},v_{j+A[j]},v_{j-A[j]} \in V_2$ with absolute differences $k$. The perfect matching will include at least one edge from $u_i$ and one edge from $u_j$. I came to the same conclusion a few times ago while thinking about the original problem, but following another way: I saw that it is easy to formulate the restricted problem as a 2-SAT formula (if you want I can add an answer with it, but mjqxxxx's idea is better). $\endgroup$ – Marzio De Biasi Dec 11 '14 at 23:06
  • $\begingroup$ @MarzioDeBiasi Why this approach (and yours) does not work for the original (unrestricted ) problem? $\endgroup$ – Mohammad Al-Turkistany Dec 12 '14 at 13:37
  • $\begingroup$ @mjqxxx I see that your approach solves the restricted case. Why can not it be extended to efficiently solve the original problem? $\endgroup$ – Mohammad Al-Turkistany Dec 12 '14 at 14:08
  • $\begingroup$ @MohammadAl-Turkistany: because in the original problem the elements of the first permutation (the $i$s in the restricted version) are not fixed, and using the same approach you end up with a tripartite graph (and in my 2-SAT approach with a $\delta_i(n) \to (\pi_i(n+A[i]) \lor \pi_i(n-A[i]))$ clause ... which is not a 2-CNF clause). $\endgroup$ – Marzio De Biasi Dec 12 '14 at 14:49
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.