Reconstruction of signed permutations from their distorted patterns

The problem of reconstructing an unknown and unique signed permutations from their distorted patterns is considered in the paper. The set of signed permutations with the reversal metric is investigated. The reversal metric is defined as the minimal number of reversals (inversions of permutation intervals with replacing signs) which are needed to transform one permutation into another. It is proved that any unknown signed permutation on elements at least two is uniquely reconstructible from three distinct signed permutations at reversal distance at most one from the unknown signed permutation. The proposed approach is based on the investigation of structural properties of a certain graph constructed for this problem. In particular, it is proved that the considered graph does not contain triangles and pentagons and does contain quadrangles. We investigate the cases when two signed permutations are sufficient to determine an unknown singed permutation uniquely. It is also shown that in the case of at most two reversal errors the reconstruction of an unknown signed permutation needs in general many more erroneous patterns