Approximating the Orthogonality Dimension of Graphs and Hypergraphs

DOI10.4230/LIPICS.MFCS.2019.39MaRDI QIDQ6320378arXivFDO

Authors Ishay Haviv

Publication date 12 June 2019

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2019.39

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

arXiv classification

cs.CCcs.DSmath.CO

Abstract: A $t$-dimensional orthogonal representation of a hypergraph is an assignment of nonzero vectors in $mathbb{R}^t$ to its vertices, such that every hyperedge contains two vertices whose vectors are orthogonal. The orthogonality dimension of a hypergraph $H$, denoted by $overlinexi(H)$, is the smallest integer $t$ for which there exists a $t$-dimensional orthogonal representation of $H$. In this paper we study computational aspects of the orthogonality dimension of graphs and hypergraphs. We prove that for every $kgeq4$, it is $mathsfNP$-hard (resp. quasi-$mathsfNP$-hard) to distinguish $n$-vertex $k$-uniform hypergraphs $H$ with $overlinexi(H)leq2$ from those satisfying $overlinexi(H)geqOmega(lo{g}^{d}eltan)$ for some constant $delta>0$ (resp. $overlinexi(H)geqOmega(lo{g}^{1-o(1)}n)$). For graphs, we relate the $mathsfNP$-hardness of approximating the orthogonality dimension to a variant of a long-standing conjecture of Stahl. We also consider the algorithmic problem in which given a graph $G$ with $overlinexi(G)leq3$ the goal is to find an orthogonal representation of $G$ of as low dimension as possible, and provide a polynomial time approximation algorithm based on semidefinite programming.

This page was built for publication: Approximating the Orthogonality Dimension of Graphs and Hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320378)