Kernelization for Orthogonality Dimension

The orthogonality dimension of a graph over R is the smallest integer d for which one can assign to every vertex a nonzero vector in Rᵈ such that every two adjacent vertices receive orthogonal vectors. For an integer d, the d-Ortho-DimR problem asks to decide whether the orthogonality dimension of a given graph over R is at most d. We prove that for every integer d ≥ 3, the d-Ortho-DimR problem parameterized by the vertex cover number k admits a kernel with O(kᵈ⁻¹) vertices and bit-size O(kᵈ⁻¹ · log k). We complement this result by a nearly matching lower bound, showing that for any ε > 0, the problem admits no kernel of bit-size O(kd-1-ε) unless NP ⊆ coNP/poly. We further study the kernelizability of orthogonality dimension problems in additional settings, including over general fields and under various structural parameterizations.