DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2024.8

Kernelization for Orthogonality Dimension

Authors: Ishay Haviv and Dror Rabinovich

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract

The orthogonality dimension of a graph over ℝ is the smallest integer d for which one can assign to every vertex a nonzero vector in ℝ^d such that every two adjacent vertices receive orthogonal vectors. For an integer d, the d-Ortho-Dim_ℝ problem asks to decide whether the orthogonality dimension of a given graph over ℝ is at most d. We prove that for every integer d ≥ 3, the d-Ortho-Dim_ℝ 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 ε > 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.

Cite as

Ishay Haviv and Dror Rabinovich. Kernelization for Orthogonality Dimension. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{haviv_et_al:LIPIcs.IPEC.2024.8,
  author =	{Haviv, Ishay and Rabinovich, Dror},
  title =	{{Kernelization for Orthogonality Dimension}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.8},
  URN =		{urn:nbn:de:0030-drops-222341},
  doi =		{10.4230/LIPIcs.IPEC.2024.8},
  annote =	{Keywords: Orthogonality dimension, Fixed-parameter tractability, Kernelization, Graph coloring}
}

Search Results

Documents authored by Rabinovich, Dror

Kernelization for Orthogonality Dimension

Abstract

Cite as

Thanks for your feedback!

Could not send message