Document Open Access Logo

Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank

Authors Dror Chawin, Ishay Haviv

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.20.pdf
  • Filesize: 0.66 MB
  • 14 pages

Document Identifiers

Author Details

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

Funding

  • Chawin, Dror: Research supported by the Israel Science Foundation (grant No. 1218/20).
  • Haviv, Ishay: Research supported by the Israel Science Foundation (grant No. 1218/20).

Acknowledgements

We thank the anonymous reviewers for their helpful comments.

Cite As Get BibTex

Dror Chawin and Ishay Haviv. Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.STACS.2023.20

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph coloring
  • Mathematics of computing → Coding theory
  • Theory of computation → Problems, reductions and completeness
Keywords
  • hardness of approximation
  • graph coloring
  • orthogonality dimension
  • minrank
  • index coding

Metrics

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

Related Versions

References

  1. Noga Alon. The Shannon capacity of a union. Combinatorica, 18(3):301-310, 1998. Google Scholar
  2. Ziv Bar-Yossef, Yitzhak Birk, T. S. Jayram, and Tomer Kol. Index coding with side information. IEEE Trans. Inform. Theory, 57(3):1479-1494, 2011. Preliminary vesrion in FOCS'06. Google Scholar
  3. Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. J. ACM, 68(4):28:1-28:66, 2021. Preliminary version in STOC'19. Google Scholar
  4. Amey Bhangale. NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors. In Proc. of the 45th International Colloquium on Automata, Languages, and Programming (ICALP'18), pages 15:1-15:11, 2018. Google Scholar
  5. Joshua Brakensiek and Venkatesan Guruswami. New hardness results for graph and hypergraph colorings. In Proc. of the 31st Conference on Computational Complexity (CCC'16), pages 14:1-14:27, 2016. Google Scholar
  6. 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
  7. Son Hoang Dau, Vitaly Skachek, and Yeow Meng Chee. Optimal index codes with near-extreme rates. IEEE Trans. Inform. Theory, 60(3):1515-1527, 2014. Preliminary version in ISIT'12. Google Scholar
  8. Ronald de Wolf. Quantum Computing and Communication Complexity. PhD thesis, Universiteit van Amsterdam, 2001. Google Scholar
  9. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843-873, 2009. Preliminary version in STOC'06. Google Scholar
  10. Irit Dinur and Igor Shinkar. On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors. In Proc. of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'10), pages 138-151, 2010. Google Scholar
  11. Michael R. Garey and David S. Johnson. The complexity of near-optimal graph coloring. J. ACM, 23(1):43-49, 1976. Google Scholar
  12. Alexander Golovnev and Ishay Haviv. The (generalized) orthogonality dimension of (generalized) Kneser graphs: Bounds and applications. Theory of Computing, 18(22):1-22, 2022. Preliminary version in CCC'21. Google Scholar
  13. Venkatesan Guruswami and Sai Sandeep. d-To-1 hardness of coloring 3-colorable graphs with O(1) colors. In Proc. of the 47th International Colloquium on Automata, Languages, and Programming, (ICALP'20), pages 62:1-62:12, 2020. Google Scholar
  14. Willem H. Haemers. On some problems of Lovász concerning the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(2):231-232, 1979. Google Scholar
  15. Willem H. Haemers. An upper bound for the Shannon capacity of a graph. In László Lovász and Vera T. Sós, editors, Algebraic Methods in Graph Theory, volume 25/I of Colloquia Mathematica Societatis János Bolyai, pages 267-272. Bolyai Society and North-Holland, 1981. Google Scholar
  16. Frank Harary and Robert Z. Norman. Some properties of line digraphs. Rend. Circ. Mat. Palermo, 9(2):161-168, 1960. Google Scholar
  17. C. C. Harner and R. C. Entringer. On the arc-chromatic number of a digraph. J. Comb. Theory, Ser. B, 13(3):219-225, 1972. Google Scholar
  18. Ishay Haviv. Approximating the orthogonality dimension of graphs and hypergraphs. In Proc. of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS'19), pages 39:1-39:15, 2019. Google Scholar
  19. Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. J. Comb. Theory, Ser. B, 48(1):92-110, 1990. Google Scholar
  20. Sangxia Huang. Improved hardness of approximating chromatic number. In Proc. of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'13), pages 233-243, 2013. Google Scholar
  21. Gil Kalai. Analogues for Sperner and Erdös-Ko-Rado theorems for subspaces of linear spaces. In Peter L. Hammer, editor, Combinatorics 79, volume 9 of Annals of Discrete Math., page 135. Elsevier, 1980. Google Scholar
  22. Richard M. Karp. Reducibility among combinatorial problems. In Proc. of a Symposium on the Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  23. 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
  24. 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
  25. Subhash Khot. Improved inaproximability results for maxclique, chromatic number and approximate graph coloring. In Proc. of the 42nd Symposium on Foundations of Computer Science (FOCS'01), pages 600-609, 2001. Google Scholar
  26. Michael Langberg and Alexander Sprintson. On the hardness of approximating the network coding capacity. IEEE Trans. Inform. Theory, 57(2):1008-1014, 2011. Preliminary version in ISIT'08. Google Scholar
  27. László Lovász. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(1):1-7, 1979. Google Scholar
  28. László Lovász. Graphs and Geometry, volume 65. Colloquium Publications, 2019. Google Scholar
  29. László Lovász, Michael Saks, and Alexander Schrijver. Orthogonal representations and connectivity of graphs. Linear Algebra Appl., 114-115:439-454, 1989. Special Issue Dedicated to Alan J. Hoffman. Google Scholar
  30. René Peeters. Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica, 16(3):417-431, 1996. Google Scholar
  31. Svatopluk Poljak and Vojtech Rödl. On the arc-chromatic number of a digraph. J. Comb. Theory, Ser. B, 31(2):190-198, 1981. Google Scholar
  32. Claude E. Shannon. The zero error capacity of a noisy channel. Institute of Radio Engineers, Trans. Inform. Theory, IT-2:8-19, 1956. Google Scholar
  33. Saul Stahl. n-tuple colorings and associated graphs. J. Comb. Theory, Ser. B, 20(2):185-203, 1976. Google Scholar
  34. Marcin Wrochna and Stanislav Živný. Improved hardness for H-colourings of G-colourable graphs. In Proc. of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'20), pages 1426-1435, 2020. Google Scholar
  35. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(1):103-128, 2007. Preliminary version in STOC'06. 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 About DROPS Imprint Privacy Contact