Permutation reconstruction from differences

MaRDI QIDQ463039zbMATH OpenFDO

Authors Marzio De Biasi

Publication date 23 October 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.6396, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p3

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

NP-completenesspermutation reconstruction

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We prove that the problem of reconstructing a permutation $p{i}_1,dotsc,p{i}_n$ of the integers $[1dotson]$ given the absolute differences $|p{i}_{i+1}-p{i}_i|$, $i=1,dotsc,n-1$ is NP-complete. As an intermediate step we first prove the NP-completeness of the decision version of a new puzzle game that we call Crazy Frog Puzzle. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.

Review text

Summary: We prove that the problem of reconstructing a permutation \(\pi_1,\ldots,\pi_n\) of the integers \([1\ldots n]\) given the absolute differences \(|\pi_{i+1}-\pi_i|\), \(i = 1,\ldots,n-1\) is \mathsf{NP}-complete. As an intermediate step we first prove the \mathsf{NP}-completeness of the decision version of a new puzzle game that we call \textit{Crazy Frog Puzzle}. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.

Recommendations

• Permutation reconstruction
• Permutation reconstruction from MinMax-betweenness constraints
• Reconstructing permutation matrices from diagonal sums
• A simple proof that the \((n^{2} - 1)\)-puzzle is hard
• Determining a permutation from its set of reductions.

Cites work

• Hamilton Paths in Grid Graphs
• scientific article; zbMATH DE number 3141308 (Why is no real title available?)
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• Permutation reconstruction
• Permutation reconstruction from minors
• Playing games with algorithms: algorithmic combinatorial game theory
• Reconstructing permutations from cycle minors

Cited in

(5)

• Permutation reconstruction from a few large patterns
• Hamiltonian problems in directed graphs with simple row patterns
• Permutation reconstruction from minors
• Improvements on permutation reconstruction from minors
• Reconstructing permutations from identification minors

This page was built for publication: Permutation reconstruction from differences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463039)