2015/03/15 by Amey Bhangale, Swastik Kopparty, Bhangale, Amey +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1503.04486
16 pages
openalex publication_date 2015/03/15 · arxiv created 2015/05/14 · arxiv updated 2015/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that computing the minimum rank of a sign pattern matrix is NP hard. Our proof is based on a simple but useful connection between minimum ranks of sign pattern matrices and the stretchability problem for pseudolines arrangements. In fact, our hardness result shows that it is already hard to determine if the minimum rank of a sign pattern matrix is ≤ 3. We complement this by giving a polynomial time algorithm for determining if a given sign pattern matrix has minimum rank ≤ 2. Our result answers one of the open problems from Linial et al. [Combinatorica, 27(4):439--463, 2007].