License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.20
URN: urn:nbn:de:0030-drops-176724
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17672/
Go to the corresponding LIPIcs Volume Portal

Chawin, Dror ; Haviv, Ishay

Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank

pdf-format:
LIPIcs-STACS-2023-20.pdf (0.7 MB)

Abstract

The orthogonality dimension of a graph G over ℝ is the smallest integer k for which one can assign a nonzero k-dimensional real vector to each vertex of G, such that every two adjacent vertices receive orthogonal vectors. We prove that for every sufficiently large integer k, it is NP-hard to decide whether the orthogonality dimension of a given graph over ℝ is at most k or at least 2^{(1-o(1))⋅k/2}. We further prove such hardness results for the orthogonality dimension over finite fields as well as for the closely related minrank parameter, which is motivated by the index coding problem in information theory. This in particular implies that it is NP-hard to approximate these graph quantities to within any constant factor. Previously, the hardness of approximation was known to hold either assuming certain variants of the Unique Games Conjecture or for approximation factors smaller than 3/2. The proofs involve the concept of line digraphs and bounds on their orthogonality dimension and on the minrank of their complement.

BibTeX - Entry

@InProceedings{chawin_et_al:LIPIcs.STACS.2023.20,
  author =	{Chawin, Dror and Haviv, Ishay},
  title =	{{Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17672},
  URN =		{urn:nbn:de:0030-drops-176724},
  doi =		{10.4230/LIPIcs.STACS.2023.20},
  annote =	{Keywords: hardness of approximation, graph coloring, orthogonality dimension, minrank, index coding}
}

Keywords: hardness of approximation, graph coloring, orthogonality dimension, minrank, index coding
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI