35
$\begingroup$

My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is NP-complete. I searched the literature without finding an equivalent or close problem.

Originally 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?

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

Cross posted on TCS SE without an answer. Efficient algorithm for existence of permutation with differences sequence?

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

$\endgroup$
11
  • 3
    $\begingroup$ +1. Great question! $\endgroup$ Jul 7, 2013 at 1:47
  • $\begingroup$ i think you should sort sequence into ascending order and if you sum adjacent elements and get distinct elements in the list then it could be difference of some permutation.is not it? $\endgroup$ Jul 7, 2013 at 6:39
  • $\begingroup$ I'm not sure that I get your idea. Do you a have an algorithm? $\endgroup$ Jul 7, 2013 at 8:49
  • $\begingroup$ The problem is NP complete it is not NP hard.It can be reduced to (in fact it is equivalent to) boolean SAT. The good news may be that your particular version just may not be in the list of NP complete problems $\endgroup$
    – ARi
    Jul 8, 2013 at 5:56
  • 1
    $\begingroup$ @ARi Could you give a reference or explanation for your claim. Also, this should then be an answer. $\endgroup$ Jul 8, 2013 at 6:22

1 Answer 1

12
$\begingroup$

I tried to give a formal proof of the NP-completeness of the problem.

For the reduction details see my answer on cstheory.stackexchange.com

$\endgroup$
1
  • $\begingroup$ I am looking forward to the addictive smartphone-app version of the Crazy Frog puzzle! $\endgroup$ Oct 27, 2014 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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