.png){kind=icon}
.png){kind=icon}
Return
Kernelization for orthogonality dimension
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jcss.2026.103757.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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-d 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) log k). We complement this result by a nearly matching lower bound, showing that for any epsilon > 0, the problem admits no kernel of bit-size O(k(d-1-epsilon)) unless NP subset of coNP/poly. We further study the kernelizability of orthogonality dimension problems in additional settings, including over general fields and under various structural parameterizations.
Keywords:
Orthogonality dimension
Fixed-parameter tractability
Kernelization
Graph coloring
Journal
J
IF:
0.9
Papers:
51
Citations:
4.5K