Document Open Access Logo

Coloring Tournaments with Few Colors: Algorithms and Complexity

Authors Felix Klingelhoefer, Alantha Newman

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.71.pdf
  • Filesize: 0.66 MB
  • 14 pages

Document Identifiers

Author Details

Felix Klingelhoefer
  • Laboratoire G-SCOP (Univ. Grenoble Alpes), Grenoble, France
Alantha Newman
  • Laboratoire G-SCOP (CNRS, Univ. Grenoble Alpes), Grenoble, France

Funding

Supported in part by ANR project DAGDigDec (ANR-21-CE48-0012).

Acknowledgements

We thank Louis Esperet for useful discussions and for his encouragement.

Cite AsGet BibTex

Felix Klingelhoefer and Alantha Newman. Coloring Tournaments with Few Colors: Algorithms and Complexity. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.71

Abstract

A k-coloring of a tournament is a partition of its vertices into k acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural problem, akin to that of coloring a 3-colorable graph with few colors, is to color a 2-colorable tournament with few colors. This problem does not seem to have been addressed before, although it is a special case of coloring a 2-colorable 3-uniform hypergraph with few colors, which is a well-studied problem with super-constant lower bounds. We present an efficient decomposition lemma for tournaments and show that it can be used to design polynomial-time algorithms to color various classes of tournaments with few colors, including an algorithm to color a 2-colorable tournament with ten colors. For the classes of tournaments considered, we complement our upper bounds with strengthened lower bounds, painting a comprehensive picture of the algorithmic and complexity aspects of coloring tournaments.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
Keywords
  • Tournaments
  • Graph Coloring
  • Algorithms
  • Complexity

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 Hariharan Ramesh. Coloring 2-colorable hypergraphs with a sublinear number of colors. Nordic Journal of Computing, 3:425-439, 1996. Google Scholar
  2. Noga Alon, János Pach, and József Solymosi. Ramsey-type theorems with forbidden subgraphs. Combinatorica, 21(2):155-170, 2001. Google Scholar
  3. Thomas Bellitto, Nicolas Bousquet, Adam Kabela, and Théo Pierron. The smallest 5-chromatic tournament. arXiv, 2022. URL: https://arxiv.org/abs/2210.09936.
  4. Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour, and Stéphan Thomassé. Tournaments and colouring. Journal of Combinatorial Theory, Series B, 103(1):1-20, 2013. Google Scholar
  5. Avrim Blum. New approximation algorithms for graph coloring. Journal of the ACM, 41(3):470-516, 1994. Google Scholar
  6. Jakub Bulín, Andrei 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
  7. Hui Chen and Alan Frieze. Coloring bipartite hypergraphs. In Fifth International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 345-358, 1996. Google Scholar
  8. Xujin Chen, Xiaodong Hu, and Wenan Zang. A min-max theorem on tournaments. SIAM Journal on Computing, 37(3):923-937, 2007. Google Scholar
  9. Maria Chudnovsky. The Erdös-Hajnal Conjecture - A survey. Journal of Graph Theory, 75(2):178-190, 2014. Google Scholar
  10. Irit Dinur, Subhash Khot, Will Perkins, and Muli Safra. Hardness of finding independent sets in almost 3-colorable graphs. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 212-221, 2010. Google Scholar
  11. Irit Dinur, Oded Regev, and Clifford Smyth. The hardness of 3-uniform hypergraph coloring. Combinatorica, 25(5):519-535, 2005. Google Scholar
  12. Paul Erdős and András Hajnal. Ramsey-type theorems. Discrete Applied Mathematics, 25(1-2):37-52, 1989. Google Scholar
  13. Paul Erdos and Leo Moser. On the representation of directed graphs as unions of orderings. Math. Inst. Hung. Acad. Sci, 9:125-132, 1964. Google Scholar
  14. Tomás Feder, Pavol Hell, and Carlos Subi. Complexity of acyclic colorings of graphs and digraphs with degree and girth constraints. arXiv, 2019. URL: https://arxiv.org/abs/1907.00061.
  15. Jacob Fox, Lior Gishboliner, Asaf Shapira, and Raphael Yuster. The removal lemma for tournaments. Journal of Combinatorial Theory, Series B, 136:110-134, 2019. Google Scholar
  16. Venkatesan Guruswami and Sanjeev Khanna. On the hardness of 4-coloring a 3-colorable graph. In Proceedings 15th Annual IEEE Conference on Computational Complexity (CCC), pages 188-197, 2000. Google Scholar
  17. Venkatesan Guruswami and Sanjeev Khanna. On the hardness of 4-coloring a 3-colorable graph. SIAM Journal on Discrete Mathematics, 18(1):30-40, 2004. Google Scholar
  18. Venkatesan Guruswami and Sai Sandeep. d-To-1 hardness of coloring 3-colorable graphs with O(1) colors. In 47th International Colloquium on Automata, Languages, and Programming (ICALP), 2020. Google Scholar
  19. Magnús M Halldórsson. A still better performance guarantee for approximate graph coloring. Information Processing Letters, 45(1):19-23, 1993. Google Scholar
  20. Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, and Stéphan Thomassé. Coloring dense digraphs. Combinatorica, 39(5):1021-1053, 2019. Google Scholar
  21. Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé, and Hehui Wu. Coloring tournaments: From local to global. Journal of Combinatorial Theory, Series B, 138:166-171, 2019. Google Scholar
  22. Johan Hastad. Clique is hard to approximate within n^1-ε. Acta Mathematica, 182:105-142, 1999. Google Scholar
  23. David R. Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM, 45(2):246-265, 1998. Google Scholar
  24. Ken-ichi Kawarabayashi and Mikkel Thorup. Coloring 3-colorable graphs with less than n^1/5 colors. Journal of the ACM, 64(1):1-23, 2017. Google Scholar
  25. Sanjeev Khanna, Nathan Linial, and Shmuel Safra. On the hardness of approximating the chromatic number. Combinatorica, 20(3):393-415, 2000. Google Scholar
  26. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 767-775, 2002. Google Scholar
  27. Subhash Khot and Rishi Saket. Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1607-1625, 2014. Google Scholar
  28. Felix Klingelhoefer and Alantha Newman. Coloring tournaments with few colors: Algorithms and complexity. arXiv, 2023. URL: https://arxiv.org/abs/2305.02922.
  29. Michael Krivelevich, Ram Nathaniel, and Benny Sudakov. Approximating coloring and maximum independent sets in 3-uniform hypergraphs. Journal of Algorithms, 41(1):99-113, 2001. Google Scholar
  30. Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. 2-Approximating feedback vertex set in tournaments. ACM Transactions on Algorithms, 17(2):1-14, 2021. Google Scholar
  31. László Lovász. Coverings and colorings of hypergraphs. In Proc. 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing, pages 3-12, 1973. Google Scholar
  32. Victor Neumann-Lara. The dichromatic number of a digraph. Journal of Combinatorial Theory, Series B, 33(3):265-270, 1982. Google Scholar
  33. Victor Neumann-Lara. The 3 and 4-dichromatic tournaments of minimum order. Discrete Mathematics, 135(1-3):233-243, 1994. Google Scholar
  34. Avi Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM, 30(4):729-735, 1983. Google Scholar
  35. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 681-690, 2006. 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