Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
Dror Chawin, Ishay Haviv · SIAM Journal on Discrete Mathematics · 2023
Abstract. The orthogonality dimension of a graph [Formula: see text] over [Formula: see text] is the smallest integer [Formula: see text] for which one can assign a nonzero [Formula: see text]-dimensional real vector to each vertex of [Formula: see text] such that every two adjacent vertices receive orthogonal vectors. We prove that for every sufficiently large integer [Formula: see text], it is [Formula: see text]-hard to decide whether the orthogonality dimension of a given graph over [Formula: see text] is at most [Formula: see text] or at least [Formula: see text]. We further prove such hardness results for the orthogonality dimension over finite fields as well as for the closely related minrank parameter, which is motivated by the index coding problem in information theory. This in particular implies that it is [Formula: see text]-hard to approximate these graph quantities to within any constant factor. Previously, the hardness of approximation was known to hold either assuming certain variants of the unique games conjecture or for approximation factors smaller than [Formula: see text]. The proofs involve the concept of line digraphs and bounds on their orthogonality dimension and on the minrank of their complement.