Document Open Access Logo

Approximating the Orthogonality Dimension of Graphs and Hypergraphs

Author Ishay Haviv

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.39.pdf
  • Filesize: 499 kB
  • 15 pages

Document Identifiers

Author Details

Ishay Haviv
  • School of Computer Science, The Academic College of Tel Aviv-Yaffo, Tel Aviv 61083, Israel

Acknowledgements

We are grateful to Alexander Golovnev for useful discussions and to the anonymous reviewers for their valuable suggestions.

Cite AsGet BibTex

Ishay Haviv. Approximating the Orthogonality Dimension of Graphs and Hypergraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.39

Abstract

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Approximation algorithms analysis
Keywords
  • orthogonal representations of hypergraphs
  • orthogonality dimension
  • hardness of approximation
  • Kneser and Schrijver graphs
  • semidefinite programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Pierre Kelsen, Sanjeev Mahajan, and Ramesh Hariharan. Approximate Hypergraph Coloring. Nord. J. Comput., 3(4):425-439, 1996. Preliminary version in SWAT'96. Google Scholar
  2. Sanjeev Arora, Eden Chlamtac, and Moses Charikar. New approximation guarantee for chromatic number. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 215-224, 2006. Google Scholar
  3. Amey Bhangale. NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), pages 15:1-15:11, 2018. Google Scholar
  4. Avrim Blum. New Approximation Algorithms for Graph Coloring. J. ACM, 41(3):470-516, 1994. Google Scholar
  5. Avrim Blum and David R. Karger. An O(n^3/14)-Coloring Algorithm for 3-Colorable Graphs. Inf. Process. Lett., 61(1):49-53, 1997. Google Scholar
  6. Joshua Brakensiek and Venkatesan Guruswami. New Hardness Results for Graph and Hypergraph Colorings. In Proceedings of the 31st Conference on Computational Complexity (CCC), pages 14:1-14:27, 2016. Google Scholar
  7. Jop Briët, Harry Buhrman, Debbie Leung, Teresa Piovesan, and Florian Speelman. Round Elimination in Exact Communication Complexity. In Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), volume 44 of LIPIcs, pages 206-225, 2015. Google Scholar
  8. Jop Briët and Jeroen Zuiddam. On the orthogonal rank of Cayley graphs and impossibility of quantum round elimination. Quantum Information & Computation, 17(1&2):106-116, 2017. Google Scholar
  9. Boris Bukh and Christopher Cox. On a Fractional Version of Haemers' Bound. IEEE Trans. Inform. Theory, 65(6):3340-3348, 2019. Google Scholar
  10. Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), pages 602-613, 2019. Google Scholar
  11. Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Severini, and Andreas J. Winter. On the Quantum Chromatic Number of a Graph. Electr. J. Comb., 14(1), 2007. Google Scholar
  12. Hui Chen and Alan M. Frieze. Coloring Bipartite Hypergraphs. In Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 345-358, 1996. Google Scholar
  13. Eden Chlamtac. Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations. In Proceedings of the 48th Symposium on Foundations of Computer Science (FOCS), pages 691-701, 2007. Google Scholar
  14. Eden Chlamtáč and Ishay Haviv. Linear Index Coding via Semidefinite Programming. Combinatorics, Probability & Computing, 23(2):223-247, 2014. Preliminary version in SODA'12. Google Scholar
  15. Ronald de Wolf. Quantum Computing and Communication Complexity. PhD thesis, Universiteit van Amsterdam, 2001. Google Scholar
  16. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional Hardness for Approximate Coloring. SIAM Journal on Computing, 39(3):843-873, 2009. Preliminary version in STOC'06. Google Scholar
  17. Irit Dinur, Oded Regev, and Clifford D. Smyth. The Hardness of 3-Uniform Hypergraph Coloring. Combinatorica, 25(5):519-535, 2005. Preliminary version in FOCS'02. Google Scholar
  18. Irit Dinur and Shmuel Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1):439-485, 2005. Preliminary version in STOC'02. Google Scholar
  19. Peter Frankl and Zoltán Füredi. Extremal problems concerning Kneser graphs. J. Comb. Theory, Ser. B, 40(3):270-284, 1986. Google Scholar
  20. Peter Frankl and Vojtěch Rödl. Forbidden intersections. Trans. Amer. Math. Soc., 300(1):259-286, 1987. Google Scholar
  21. Michael R. Garey and David S. Johnson. The Complexity of Near-Optimal Graph Coloring. J. ACM, 23(1):43-49, 1976. Google Scholar
  22. Chris D. Godsil and Joseph Zaks. Colouring the Sphere. University of Waterloo research report, CORR 88-12, 1988. Google Scholar
  23. Alexander Golovnev, Oded Regev, and Omri Weinstein. The Minrank of Random Graphs. IEEE Trans. Inform. Theory, 64(11):6990-6995, 2018. Preliminary version in RANDOM'17. Google Scholar
  24. Venkatesan Guruswami, Johan Håstad, and Madhu Sudan. Hardness of Approximate Hypergraph Coloring. SIAM J. Comput., 31(6):1663-1686, 2002. Preliminary version in FOCS'00. Google Scholar
  25. Venkatesan Guruswami and Sanjeev Khanna. On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM J. Discrete Math., 18(1):30-40, 2004. Preliminary version in CCC'00. Google Scholar
  26. Willem H. Haemers. An upper bound for the Shannon capacity of a graph. In Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), volume 25 of Colloq. Math. Soc. János Bolyai, pages 267-272. North-Holland, Amsterdam, 1981. Google Scholar
  27. Eran Halperin, Ram Nathaniel, and Uri Zwick. Coloring k-colorable graphs using relatively small palettes. J. Algorithms, 45(1):72-90, 2002. Preliminary version in SODA'01. Google Scholar
  28. Ishay Haviv. Topological Bounds on the Dimension of Orthogonal Representations of Graphs. Eur. J. Comb., 81:84-97, 2019. Google Scholar
  29. David R. Karger, Rajeev Motwani, and Madhu Sudan. Approximate Graph Coloring by Semidefinite Programming. J. ACM, 45(2):246-265, 1998. Preliminary version in FOCS'94. Google Scholar
  30. Richard M. Karp. Reducibility Among Combinatorial Problems. In Proceedings of a Symposium on the Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  31. Ken-ichi Kawarabayashi and Mikkel Thorup. Coloring 3-Colorable Graphs with Less than n^1/5 Colors. J. ACM, 64(1):4:1-4:23, 2017. Preliminary versions in FOCS'12 and STACS'14. Google Scholar
  32. Sanjeev Khanna, Nathan Linial, and Shmuel Safra. On the Hardness of Approximating the Chromatic Number. Combinatorica, 20(3):393-415, 2000. Preliminary version in ISTCS'93. Google Scholar
  33. Martin Kneser. Aufgabe 360. Jahresbericht der Deutschen Mathematiker-Vereinigung, 58(2):27, 1955. Google Scholar
  34. Simon Kochen and E. P. Specker. The Problem of Hidden Variables in Quantum Mechanics. Journal of Mathematics and Mechanics, 17(1):59-87, 1967. Google Scholar
  35. Michael Krivelevich, Ram Nathaniel, and Benny Sudakov. Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs. J. Algorithms, 41(1):99-113, 2001. Preliminary version in SODA'01. Google Scholar
  36. László Lovász. Coverings and colorings of hypergraphs. In Proceedings of the 4th Southeastern Conf. on Comb., pages 3-12. Utilitas Math., 1973. Google Scholar
  37. László Lovász. Kneser’s Conjecture, Chromatic Number, and Homotopy. J. Comb. Theory, Ser. A, 25(3):319-324, 1978. Google Scholar
  38. László Lovász. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(1):1-7, 1979. Google Scholar
  39. László Lovász. Chapter 5: Orthogonal representations and their dimension. Lecture notes: Selected topics in graph theory, 2016. Available at https://http://web.cs.elte.hu/ lovasz/kurzusok/orth16-2.pdf. Google Scholar
  40. László Lovász, Michael Saks, and Alexander Schrijver. Orthogonal representations and connectivity of graphs. Linear Algebra and its Applications, 114/115:439-454, 1989. Special Issue Dedicated to Alan J. Hoffman. Google Scholar
  41. Dana Moshkovitz and Ran Raz. Two-query PCP with subconstant error. J. ACM, 57(5):29:1-29:29, 2010. Preliminary version in FOCS'08. Google Scholar
  42. René Peeters. Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica, 16(3):417-431, 1996. Google Scholar
  43. Giannicola Scarpa and Simone Severini. Kochen-Specker sets and the rank-1 quantum chromatic number. IEEE Trans. Inform. Theory, 58(4):2524-2529, 2012. Google Scholar
  44. Alexander Schrijver. Vertex-critical subgraphs of Kneser graphs. Nieuw Arch. Wiskd., 26(3):454-461, 1978. Google Scholar
  45. Saul Stahl. n-Tuple colorings and associated graphs. J. Comb. Theory, Ser. B, 20(2):185-203, 1976. Google Scholar
  46. Saul Stahl. The multichromatic numbers of some Kneser graphs. Discrete Mathematics, 185(1-3):287-291, 1998. Google Scholar
  47. Avi Wigderson. Improving the Performance Guarantee for Approximate Graph Coloring. J. ACM, 30(4):729-735, 1983. Preliminary version in STOC'82. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact