  A matrix is incomplete when some of its entries are missing. A Robinson
incomplete symmetric matrix is an incomplete symmetric matrix whose non-missing
entries do not decrease along rows and columns when moving toward the diagonal.
A Strong-Robinson incomplete symmetric matrix is an incomplete symmetric matrix
$A$ such that $a_{k,l} \geq a_{i,j}$ if $a_{i,j}$ and $a_{k,l}$ are two
non-missing entries of $A$ and $i\leq k \leq l \leq j$. On the other hand, an
incomplete symmetric matrix is Strong-Robinsonian if there is a simultaneous
reordering of its rows and columns that produces a Strong-Robinson matrix. In
this document, we first show that there is an incomplete Robinson matrix which
is not Strong-Robinsonian. Therefore, these two definitions are not equivalent.
Secondly, we study the recognition problem for Strong-Robinsonian incomplete
matrices. It is known that recognition of incomplete Robinsonian matrices is
NP-Complete. We show that the recognition of incomplete Strong-Robinsonian
matrices is also NP-Complete. However, we show that recognition of
Strong-Robinsonian matrices can be parametrized with respect to the number of
missing entries. Indeed, we present an $O(|w|^bn^2)$ recognition algorithm for
Strong-Robinsonian matrices, where $b$ is the number of missing entries, $n$ is
the size of the matrix, and $|w|$ is the number of different values in the
matrix.
