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.

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

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

Cited in

(4)

• Hamiltonian problems in directed graphs with simple row patterns
• Reconstructing permutations from identification minors
• Permutation reconstruction from a few large patterns
• Permutation reconstruction from 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)