On the Recognition of Strong-Robinsonian Incomplete Matrices

arXiv2101.03033MaRDI QIDQ6357849FDOQ6357849

Julio Aracena, Christopher Thraves Caro

Publication date: 8 January 2021

Abstract: 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 $ileqkleqlleqj$. 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{|}^b{n}^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.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General topics of discrete mathematics in relation to computer science (68R01) Parameterized complexity, tractability and kernelization (68Q27)

This page was built for publication: On the Recognition of Strong-Robinsonian Incomplete Matrices

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