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^d-1) vertices and bit-size O (k^d-1 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 (k^d-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.