Kernelization for Orthogonality Dimension
<|reference_start|>Kernelization for Orthogonality Dimension: The orthogonality dimension of a graph over $\mathbb{R}$ is the smallest integer $d$ for which one can assign to every vertex a nonzero vector in $\mathbb{R}^d$ such that every two adjacent vertices receive orthogonal vectors. For an integer $d$, the $d$-Ortho-Dim$_\mathbb{R}$ problem asks to decide whether the orthogonality dimension of a given graph over $\mathbb{R}$ is at most $d$. We prove that for every integer $d \geq 3$, the $d$-Ortho-Dim$_\mathbb{R}$ problem parameterized by the vertex cover number $k$ admits a kernel with $O(k^{d-1})$ vertices and bit-size $O(k^{d-1} \cdot \log k)$. We complement this result by a nearly matching lower bound, showing that for any $\varepsilon > 0$, the problem admits no kernel of bit-size $O(k^{d-1-\varepsilon})$ unless $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. We further study the kernelizability of orthogonality dimension problems in additional settings, including over general fields and under various structural parameterizations.<|reference_end|>
@article{haviv2024kernelization,
    title={Kernelization for Orthogonality Dimension},
    author={Ishay Haviv and Dror Rabinovich},
    journal={arXiv preprint arXiv:2408.08380},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.08380},
    primaryClass={cs.DS}
}