Document Open Access Logo

On Percolation and NP-Hardness

Authors Huck Bennett, Daniel Reichman, Igor Shinkar

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.80.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Huck Bennett
Daniel Reichman
Igor Shinkar

Cite As Get BibTex

Huck Bennett, Daniel Reichman, and Igor Shinkar. On Percolation and NP-Hardness. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.80

Abstract

The edge-percolation and vertex-percolation random graph models start with an arbitrary graph G, and randomly delete edges or vertices of G with some fixed probability. We study the computational hardness of problems whose inputs are obtained by applying percolation to worst-case instances. Specifically, we show that a number of classical N P-hard graph problems remain essentially as hard on percolated instances as they are in the worst-case (assuming NP !subseteq BPP). We also prove hardness results for other NP-hard problems such as Constraint Satisfaction Problems, where random deletions are applied to clauses or variables.

We focus on proving the hardness of the Maximum Independent Set problem and the Graph Coloring problem on percolated instances. To show this we establish the robustness of the corresponding parameters alpha(.) and Chi(.) to percolation, which may be of independent interest. Given a graph G, let G' be the graph obtained by randomly deleting edges of G. We show that if alpha(G) is small, then alpha(G') remains small with probability at least 0.99. Similarly, we show that if Chi(G) is large, then Chi(G') remains large with probability at least 0.99.

Subject Classification

Keywords
  • percolation
  • NP-hardness
  • random subgraphs
  • chromatic number

Metrics

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

References

  1. N. Alon and J. H. Spencer. The Probabilistic Method. Wiley-Interscience series in discrete mathematics and optimization. J. Wiley &Sons, New York, 2000. Google Scholar
  2. B. Barak, M. Hardt, T. Holenstein, and Steurer D. Subsampling mathematical relaxations and average-case complexity. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, San Francisco, California, USA, pages 512-531, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.41.
  3. B. Bollobás. The chromatic number of random graphs. Combinatorica, 8(1):49-55, 1988. URL: http://dx.doi.org/10.1007/BF02122551.
  4. B. Bollobás. Random graphs. Springer, 1998. Google Scholar
  5. B. Bollobás, B. P. Narayanan, and A. M. Raigorodskii. On the stability of the erdős-ko-rado theorem. J. Comb. Theory, Ser. A, 137:64-78, 2016. URL: http://dx.doi.org/10.1016/j.jcta.2015.08.002.
  6. R. L. Brooks. On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37:194-197, 4 1941. URL: http://dx.doi.org/10.1017/S030500410002168X.
  7. B. Bukh. Interesting problems that I cannot solve. Problem 2. URL: http://www.borisbukh.org/problems.html.
  8. I. Dinur, E. Mossel, and O. Regev. Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843-873, 2009. URL: http://dx.doi.org/10.1137/07068062X.
  9. I. Dinur and I. Shinkar. On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, pages 138-151, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15369-3_11.
  10. M. Etscheid and H. Röglin. Smoothed analysis of local search for the maximum-cut problem. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, Portland, Oregon, USA, pages 882-889, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.66.
  11. U. Feige and J. Kilian. Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57(2):187-199, 1998. URL: http://dx.doi.org/10.1006/jcss.1998.1587.
  12. U. Feige and Daniel Reichman. Recoverable values for independent sets. Random Struct. Algorithms, 46(1):142-159, 2015. URL: http://dx.doi.org/10.1002/rsa.20492.
  13. A. M. Frieze and C. McDiarmid. Algorithmic theory of random graphs. Random Struct. Algorithms, 10(1-2):5-42, 1997. URL: http://dx.doi.org/10.1002/(SICI)1098-2418(199701/03)10:1/2<5::AID-RSA2>3.0.CO;2-Z.
  14. M. R. Garey and D. S. Johnson. The complexity of near-optimal graph coloring. J. ACM, 23(1):43-49, January 1976. URL: http://dx.doi.org/10.1145/321921.321926.
  15. G. Grimmett. Percolation. Springer, 1999. Google Scholar
  16. G. R. Grimmett and C. J. H. McDiarmid. On colouring random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 77:313-324, 3 1975. URL: http://dx.doi.org/10.1017/S0305004100051124.
  17. S. Har-Peled. Concentration of Random Variables - Chernoff’s Inequality. Available at URL: http://sarielhp.org/teach/13/b_574_rand_alg/lec/07_chernoff.pdf.
  18. S. Huang. Improved hardness of approximating chromatic number. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, pages 233-243, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40328-6_17.
  19. D. R. Karger. Random sampling in cut, flow, and network design problems. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, Montréal, Québec, Canada, pages 648-657, 1994. URL: http://dx.doi.org/10.1145/195058.195422.
  20. S. Khot. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 600-609, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959936.
  21. L. Kucera. The greedy coloring is a bad probabilistic algorithm. J. Algorithms, 12(4):674-684, 1991. Google Scholar
  22. T. Łuczak. The chromatic number of random graphs. Combinatorica, 11(1):45-54, 1991. URL: http://dx.doi.org/10.1007/BF01375472.
  23. M. Mezard and A. Montanari. Information, physics, and computation. Oxford University Press, 2009. Google Scholar
  24. S. Misra. Decay of Correlation and Inference in Graphical Models. PhD thesis, MIT, 2014. Google Scholar
  25. E. Mossel, R. O'Donnell, O. Regev, J. E. Steif, and B. Sudakov. Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality. Israel Journal of Mathematics, 154:299-336, 2006. Google Scholar
  26. O. Sisask. Discrete fourier analysis. Available at URL: https://people.kth.se/~sisask/Shillong/DFA_2.pdf.
  27. A. Sly. Computational transition at the uniqueness threshold. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, USA, pages 287-296, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.34.
  28. D. A. Spielman and S-H. Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385-463, 2004. URL: http://dx.doi.org/10.1145/990308.990310.
  29. D. A. Spielman and S-H. Teng. Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM, 52(10):76-84, 2009. URL: http://dx.doi.org/10.1145/1562764.1562785.
  30. V. V. Vazirani. Approximation Algorithms. Springer-Verlag New York, Inc., New York, NY, USA, 2001. 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