  We solve the recognition problem (RP) for the class of Demidenko matrices.
Our result closes a remarkable gap in the recognition of specially structured
matrices. Indeed, the recognition of permuted Demidenko matrices is a
longstanding open problem, in contrast to the effciently solved RP for
important subclasses of Demidenko matrices such as the Kalmanson matrices, the
Supnick matrices, the Monge matrices and the Anti-Robinson matrices. The
recognition of the permuted Demidenko matrices is relevant in the context of
hard combinatorial optimization problems which become tractable if the input is
a Demidenko matrix. Demidenko matrices were introduced by Demidenko in 1976,
when he proved that the Travelling Salesman Problem (TSP) is polynomially
solvable if the symmetric distance matrix fulfills certain combinatorial
conditions, nowadays known as the Demidenko conditions. In the context of the
TSP the recognition problem consists in deciding whether there is a renumbering
of the cities such that the correspondingly renumbered distance matrix fulfills
the Demidenko conditions, thus resulting in a polynomially solvable special
case of the TSP. We show that such a renumbering of n cities can be found in
$O(n^4)$ time, if it exists.
