12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Jul 5 '13 at 15:04
  • 2
    $\begingroup$ @MarzioDeBiasi It think you share my passion for permutation problems. I hope that I came up with the simplest computationally interesting permutation problem :) $\endgroup$ – Mohammad Al-Turkistany Jul 5 '13 at 15:43
  • 2
    $\begingroup$ :-) ... 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. $\endgroup$ – Marzio De Biasi Jul 5 '13 at 16:11
  • $\begingroup$ @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. $\endgroup$ – Mohammad Al-Turkistany Feb 22 '14 at 9:06
10
+50
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Nice, I am sure this will lead to a solution, the selection gadget is definitely realizable. $\endgroup$ – domotorp Jul 12 '13 at 7:45
  • $\begingroup$ @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 :-) $\endgroup$ – Marzio De Biasi Jul 12 '13 at 10:35
  • $\begingroup$ @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? $\endgroup$ – Mohammad Al-Turkistany Jul 12 '13 at 11:01
  • $\begingroup$ @MarzioDeBiasi Could you post your final answer (formal) before the bounty expires? $\endgroup$ – Mohammad Al-Turkistany Jul 14 '13 at 22:18
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Jul 20 '13 at 20:41

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.