Document Open Access Logo

NP-Hardness of Almost Coloring Almost 3-Colorable Graphs

Authors Yahli Hecht , Dor Minzer , Muli Safra

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2023.51.pdf
  • Filesize: 0.72 MB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • PCP
  • Hardness of approximation

Metrics

Abstract

A graph G = (V,E) is said to be (k,δ) almost colorable if there is a subset of vertices V' ⊆ V of size at least (1-δ)|V| such that the induced subgraph of G on V' is k-colorable. We prove that for all k, there exists δ > 0 such for all ε > 0, given a graph G it is NP-hard (under randomized reductions) to distinguish between:  
1) Yes case: G is (3,ε) almost colorable. 
2) No case: G is not (k,δ) almost colorable.  This improves upon an earlier result of Khot et al. [Irit Dinur et al., 2018], who showed a weaker result wherein in the "yes case" the graph is (4,ε) almost colorable.

Cite As Get BibTex

Yahli Hecht, Dor Minzer, and Muli Safra. NP-Hardness of Almost Coloring Almost 3-Colorable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 51:1-51:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.51

Author Details

Yahli Hecht
  • School of Computer Science, Tel Aviv University, Israel
Dor Minzer
  • Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA
Muli Safra
  • School of Computer Science, Tel Aviv University, Israel

Funding

  • Hecht, Yahli: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 835152).
  • Minzer, Dor: Supported by an Sloan Research Fellowship, NSF CCF award 2227876 and NSF CAREER award 2239160.
  • Safra, Muli: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 835152), and by an ISF grant and a BSF grant.

References

  1. Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of vertex cover and independent set in bounded degree graphs. Theory Comput., 7(1):27-43, 2011. URL: https://doi.org/10.4086/toc.2011.v007a003.
  2. Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Oprsal. Algebraic approach to promise constraint satisfaction. J. ACM, 68(4):28:1-28:66, 2021. URL: https://doi.org/10.1145/3457606.
  3. Mark Braverman, Subhash Khot, Noam Lifshitz, and Dor Minzer. An invariance principle for the multi-slice, with applications. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 228-236. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00030.
  4. Mark Braverman, Subhash Khot, and Dor Minzer. On rich 2-to-1 games. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 27:1-27:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.27.
  5. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. On non-optimally expanding sets in grassmann graphs. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 940-951. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188806.
  6. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 376-389. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188804.
  7. Irit Dinur, Elchanan Mossel, and Oded Regev. Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843-873, 2009. URL: https://doi.org/10.1137/07068062X.
  8. Venkatesan Guruswami and Sai Sandeep. d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 62:1-62:12, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.62.
  9. C.C Harner and R.C Entringer. Arc colorings of digraphs. Journal of Combinatorial Theory, Series B, 13(3):219-225, 1972. URL: https://doi.org/10.1016/0095-8956(72)90057-3.
  10. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  11. Ken-ichi Kawarabayashi and Mikkel Thorup. Coloring 3-colorable graphs with less than n 1/5 colors. Journal of the ACM (JACM), 64(1):1-23, 2017. Google Scholar
  12. Sanjeev Khanna, Nathan Linial, and Shmuel Safra. On the hardness of approximating the chromatic number. In Second Israel Symposium on Theory of Computing Systems, ISTCS 1993, Natanya, Israel, June 7-9, 1993, Proceedings, pages 250-260. IEEE Computer Society, 1993. URL: https://doi.org/10.1109/ISTCS.1993.253464.
  13. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, page 25. IEEE Computer Society, 2002. URL: https://doi.org/10.1109/CCC.2002.1004334.
  14. Subhash Khot. On the proof of the 2-to-2 games conjecture. Current Developments in Mathematics, 2019(1):43-94, 2019. Google Scholar
  15. Subhash Khot, Dor Minzer, and Muli Safra. On independent sets, 2-to-2 games, and grassmann graphs. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 576-589. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055432.
  16. Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in grassmann graph have near-perfect expansion. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 592-601. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00062.
  17. Andrei Krokhin, Jakub Oprš al, Marcin Wrochna, and Stanislav Živný. Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing, 52(1):38-79, February 2023. URL: https://doi.org/10.1137/20m1378223.
  18. Dor Minzer. On Monotonicity Testing and the 2-to-2 Games Conjecture, volume 49. Association for Computing Machinery, New York, NY, USA, 1 edition, 2022. Google Scholar
  19. Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. Google Scholar
  20. S. Poljak and V. Rödl. On the arc-chromatic number of a digraph. Journal of Combinatorial Theory, Series B, 31(2):190-198, 1981. URL: https://doi.org/10.1016/S0095-8956(81)80024-X.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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