Document Open Access Logo

Linearly Ordered Colourings of Hypergraphs

Authors Tamio-Vesa Nakajima , Stanislav Živný

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.128.pdf
  • Filesize: 0.85 MB
  • 18 pages

Document Identifiers

Author Details

Tamio-Vesa Nakajima
  • Department of Computer Science, University of Oxford, UK
Stanislav Živný
  • Department of Computer Science, University of Oxford, UK

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.

Cite As Get BibTex

Tamio-Vesa Nakajima and Stanislav Živný. Linearly Ordered Colourings of Hypergraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 128:1-128:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.128

Abstract

A linearly ordered (LO) k-colouring of an r-uniform hypergraph assigns an integer from {1, …, k} to every vertex so that, in every edge, the (multi)set of colours has a unique maximum. Equivalently, for r = 3, if two vertices in an edge are assigned the same colour, then the third vertex is assigned a larger colour (as opposed to a different colour, as in classic non-monochromatic colouring). Barto, Battistelli, and Berg [STACS'21] studied LO colourings on 3-uniform hypergraphs in the context of promise constraint satisfaction problems (PCSPs). We show two results. 
First, given a 3-uniform hypergraph that admits an LO 2-colouring, one can find in polynomial time an LO k-colouring with k = O(√{nlog log n}/log n), where n is the number of vertices of the input hypergraph. This is established by building on ideas from algorithms designed for approximate graph colourings.
Second, given an r-uniform hypergraph that admits an LO 2-colouring, we establish NP-hardness of finding an LO 3-colouring for every constant uniformity r ≥ 5. In fact, we determine the precise relationship of polymorphism minions for all uniformities r ≥ 3, which reveals a key difference between r = 3,4 and r ≥ 5 and which may be of independent interest. Using the algebraic approach to PCSPs, we actually show a more general result establishing NP-hardness of finding an LO (k+1)-colouring for LO k-colourable r-uniform hypergraphs for k ≥ 2 and r ≥ 5.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Constraint and logic programming
Keywords
  • hypegraph colourings
  • promise constraint satisfaction
  • PCSP
  • polymorphisms
  • minions
  • algebraic approach

Metrics

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

Related Versions

References

  1. Per Austrin, Amey Bhangale, and Aditya Potukuchi. Simplified inpproximability of hypergraph coloring via t-agreeing families, 2019. Google Scholar
  2. Per Austrin, Amey Bhangale, and Aditya Potukuchi. Improved inapproximability of rainbow coloring. In Proc. 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'20), pages 1479-1495, 2020. URL: https://doi.org/10.1137/1.9781611975994.90.
  3. Per Austrin, Venkatesan Guruswami, and Johan Håstad. (2+ε)-Sat is NP-hard. SIAM J. Comput., 46(5):1554-1573, 2017. URL: https://doi.org/10.1137/15M1006507.
  4. Libor Barto, Diego Battistelli, and Kevin M. Berg. Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case. In Proc. 38th International Symposium on Theoretical Aspects of Computer Science (STACS'21), volume 187 of LIPIcs, pages 10:1-10:16, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.10.
  5. 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. URL: https://doi.org/10.1145/3457606.
  6. Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.1.
  7. Libor Barto, Jakub Opršal, and Michael Pinsker. The wonderland of reflections. Isr. J. Math, 223(1):363-398, February 2018. URL: https://doi.org/10.1007/s11856-017-1621-9.
  8. Bonnie Berger and John Rompel. A better performance guarantee for approximate graph coloring. Algorithmica, 5(3):459-466, 1990. URL: https://doi.org/10.1007/BF01840398.
  9. Amey Bhangale. NP-Hardness of Coloring 2-Colorable Hypergraph with Poly-Logarithmically Many Colors. In Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP'18), volume 107 of LIPIcs, pages 15:1-15:11, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.15.
  10. Joshua Brakensiek and Venkatesan Guruswami. New hardness results for graph and hypergraph colorings. In Proc. 31st Conference on Computational Complexity (CCC'16), volume 50 of LIPIcs, pages 14:1-14:27, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.14.
  11. Joshua Brakensiek and Venkatesan Guruswami. Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. SIAM J. Comput., 50(6):1663-1700, 2021. URL: https://doi.org/10.1137/19M128212X.
  12. Joshua Brakensiek and Venkatesan Guruswami. The quest for strong inapproximability results with perfect completeness. ACM Trans. Algorithms, 17(3):27:1-27:35, 2021. URL: https://doi.org/10.1145/3459668.
  13. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. Google Scholar
  14. Irit Dinur, Oded Regev, and Clifford Smyth. The hardness of 3-uniform hypergraph coloring. Comb., 25(5):519-535, September 2005. URL: https://doi.org/10.1007/s00493-005-0032-4.
  15. Irit Dinur and Igor Shinkar. On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors. In Proc. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'10), volume 6302 of LNCS, pages 138-151. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15369-3_11.
  16. M. R. Garey and D. S. Johnson. The complexity of near-optimal graph coloring. J. ACM, 23(1):43-49, 1976. URL: https://doi.org/10.1145/321921.321926.
  17. Venkatesan Guruswami and Sanjeev Khanna. On the hardness of 4-coloring a 3-colorable graph. SIAM J. Discret. Math, 18(1):30-40, 2004. URL: https://doi.org/10.1137/S0895480100376794.
  18. Venkatesan Guruswami and Euiwoong Lee. Strong inapproximability results on balanced rainbow-colorable hypergraphs. Comb., 38(3):547-599, 2018. URL: https://doi.org/10.1007/s00493-016-3383-0.
  19. Venkatesan Guruswami and Sai Sandeep. Rainbow coloring hardness via low sensitivity polymorphisms. SIAM J. Discret. Math, 34(1):520-537, 2020. URL: https://doi.org/10.1137/19M127731X.
  20. Venkatesan Guruswami and Luca Trevisan. The complexity of making unique choices: Approximating 1-in- k SAT. In Proc. 8th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'05), volume 3624 of LNCS, pages 99-110. Springer, 2005. URL: https://doi.org/10.1007/11538462_9.
  21. Magnús M. Halldórsson. Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Apppl., 4(1):1-16, 2000. URL: https://doi.org/10.7155/jgaa.00020.
  22. Sangxia Huang. Improved hardness of approximating chromatic number. In Proc. 16th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX'13), pages 233-243. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40328-6_17.
  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. URL: https://doi.org/10.1145/3001582.
  24. Sanjeev Khanna, Nathan Linial, and Shmuel Safra. On the hardness of approximating the chromatic number. Comb., 20(3):393-415, March 2000. URL: https://doi.org/10.1007/s004930070013.
  25. Tamio-Vesa Nakajima and Stanislav Živný. Linearly ordered colourings of hypergraphs, 2022. URL: http://arxiv.org/abs/2204.05628.
  26. Avi Wigderson. Improving the performance guarantee for approximate graph coloring. J. ACM, 30(4):729-735, 1983. URL: https://doi.org/10.1145/2157.2158.
  27. Marcin Wrochna and Stanislav Živný. Improved hardness for H-colourings of G-colourable graphs. In Proc. 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'20), pages 1426-1435, 2020. URL: https://doi.org/10.1137/1.9781611975994.86.
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