2026-07-23T00:29:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10983 2024-03-06T10:46:58Z ddc:004 open_access

Approximating the Orthogonality Dimension of Graphs and Hypergraphs Haviv, Ishay orthogonal representations of hypergraphs orthogonality dimension hardness of approximation Kneser and Schrijver graphs semidefinite programming A t-dimensional orthogonal representation of a hypergraph is an assignment of nonzero vectors in 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 overline{xi}(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 k >= 4, it is NP-hard (resp. quasi-NP-hard) to distinguish n-vertex k-uniform hypergraphs H with overline{xi}(H) <= 2 from those satisfying overline{xi}(H) >= Omega(log^delta n) for some constant delta>0 (resp. overline{xi}(H) >= Omega(log^{1-o(1)} n)). For graphs, we relate the NP-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 overline{xi}(G) <= 3 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ishay Haviv 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.39 urn:nbn:de:0030-drops-109836 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.39 eng https://creativecommons.org/licenses/by/3.0/legalcode