Consecutive ones Block for Symmetric Matrices
Rui Wang, C. M. Lau · 2003
We show that a cubic graph G with girth g(G) >= 5 has a Hamiltonian Circuit if and only if the matrix A+ I can be row permuted such that each column has at most 2 blocks of consecutive 1's, where A is the adjacency matrix of G, I is the unit matrix, and a block can be consecutive in circular sense, i.e., the first row and the last row are viewed as adjacent rows. Then, based on this necessary and sufficient condition and the NP-completeness of Hamiltonian Circuit for cubic graphs [2], we prove that for every fixed k 2 the k-Consecutive Blocks problem (deciding whether a given binary matrix M can be permuted on rows such that each column has at most k blocks of consecutive 1's) remains NP-Complete even if restricted to (1) symmetric matrices, or (2) matrices having at most 3 blocks of consecutive 1's per row. This result significantly generalizes the related results of [5, 6], and gets its application in [9] in proving the NP-Completeness of all shortest paths Interval Routing Schemes with compactness k for every k 3.