Document Open Access Logo

Smoothed Analysis on Connected Graphs

Authors Michael Krivelevich, Daniel Reichman, Wojciech Samotij

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.810.pdf
  • Filesize: 491 kB
  • 16 pages

Document Identifiers

Author Details

Michael Krivelevich
Daniel Reichman
Wojciech Samotij

Cite As Get BibTex

Michael Krivelevich, Daniel Reichman, and Wojciech Samotij. Smoothed Analysis on Connected Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 810-825, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.810

Abstract

The main paradigm of smoothed analysis on graphs suggests that for any large graph G in a certain class of graphs, perturbing slightly the edges of G at random (usually adding few random edges to G) typically results in a graph having much "nicer" properties. In this work we study smoothed analysis on trees or, equivalently, on connected graphs. Given an n-vertex connected graph G, form a random supergraph of G* of G by turning every pair of vertices of G into an edge with probability epsilon/n, where epsilon is a small positive constant. This perturbation model has been studied previously in several contexts, including smoothed analysis, small world networks, and combinatorics.

Connected graphs can be bad expanders, can have very large diameter, and possibly contain no long paths. In contrast, we show that if G is an n-vertex connected graph then typically G* has edge expansion Omega(1/(log n)), diameter O(log n), vertex expansion Omega(1/(log n)), and contains a path of length Omega(n), where for the last two properties we additionally assume that G has bounded maximum degree. Moreover, we show that if G has bounded degeneracy, then typically the mixing time of the lazy random walk on G* is O(log^2(n)). All these results are asymptotically tight.

Subject Classification

Keywords
  • Random walks and Markov chains
  • Random network models

Metrics

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

References

  1. L. Addario-Berry and T. Lei. The mixing time of the Newman-Watts small world. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'12, pages 1661-1668, 2012. Google Scholar
  2. M. Ajtai, J. Komlós, and E. Szemerédi. The longest path in a random graph. Combinatorica, 1:1-12, 1981. Google Scholar
  3. I. Benjamini, G. Kozma, and N. Wormald. The mixing time of the giant component of a random graph. arXiv:math/0610459 [math.PR]. Google Scholar
  4. I. Benjamini and E. Mossel. On the mixing time of a simple random walk on the super critical percolation cluster. Probab. Theory Related Fields, 125:408-420, 2003. Google Scholar
  5. A. Blum and J. Dunagan. Smoothed analysis of the perceptron algorithm for linear programming. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'02, pages 905-914, 2002. Google Scholar
  6. A. Blum and J. Spencer. Coloring random and semi-random k-colorable graphs. J. Algorithms, 19:204-234, 1995. Google Scholar
  7. F. Bohman, A. Frieze, and R. Martin. How many random edges make a dense graph hamiltonian? Random Structures Algorithms, 22:33-42, 2003. Google Scholar
  8. B. Bollobás and F. R. Chung. The diameter of a cycle plus a random matching. SIAM J. Discrete Math., 1:328-333, 1988. Google Scholar
  9. A. Coja-Oghlan, U. Feige, A. Frieze, M. Krivelevich, and D. Vilenchik. On Smoothed k-CNF Formulas and the Walksat Algorithm. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'09, pages 451-460, 2009. Google Scholar
  10. J. Ding and Y. Peres. Sensitivity of mixing times. Electron. Commun. Probab., 18:1-6, 2013. Google Scholar
  11. R. Durrett. Random graph dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2010. Google Scholar
  12. U. Feige. Refuting Smoothed 3CNF Formulas. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS' 07, pages 407-417, 2007. Google Scholar
  13. U. Feige and J. Kilian. Heuristics for semirandom graph problems. J. Comput. System Sci., 63:639-671, 2001. Google Scholar
  14. A. Flaxman and A. Frieze. The diameter of randomly perturbed digraphs and some applications. Random Structures Algorithms, 30:484-504, 2007. Google Scholar
  15. A. D. Flaxman. Expansion and lack thereof in randomly perturbed graphs. Internet Math., 4:131-147, 2007. Google Scholar
  16. N. Fountoulakis and B. A. Reed. Faster mixing and small bottlenecks. Probab. Theory Related Fields, 137:475-486, 2007. Google Scholar
  17. N. Fountoulakis and B. A. Reed. The evolution of the mixing rate of a simple random walk on the giant component of a random graph. Random Structures Algorithms, 33:68-86, 2008. Google Scholar
  18. M. Jerrum and A. Sinclair. Conductance and the rapid mixing property for markov chains: the approximation of the permanent resolved. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC'88, pages 235-244, 1988. Google Scholar
  19. M. Krivelevich and A. Nachmias. Coloring complete bipartite graphs from random lists. Random Structures Algorithms, 29:436-449, 2006. Google Scholar
  20. M. Krivelevich and B. Sudakov. The phase transition in random graphs - a simple proof. Random Structures Algorithms, 43:1-15, 2013. Google Scholar
  21. M. Krivelevich, B. Sudakov, and P. Tetali. On smoothed analysis in dense graphs and formulas. Random Structures Algorithms, 29:180-193, 2006. Google Scholar
  22. D. A. Levin, Y. Peres, and E. L. Wilmer. Markov chains and mixing times. American Mathematical Society, Providence, RI, 2009. Google Scholar
  23. M. Mitzenmacher and E. Upfal. Probability and Computing, Randomized algorithms and probabilistic analysis. Cambridge University Press, Cambridge, 2005. Google Scholar
  24. M. E. J. Newman and D. J. Watts. Renormalization group analysis of the small-world network model. Phys. Lett. A, 263:341-346, 1999. Google Scholar
  25. M. E. J. Newman and D. J. Watts. Scaling and percolation in the small-world network model. Phys. Rev. E (3), 60:7332-7342, 1999. Google Scholar
  26. A. Sankar, D. Spielman, and S. H. Teng. Smoothed analysis of the condition numbers and growth factors of matrices. SIAM J. Matrix Anal. Appl., 28:446-476, 2006. Google Scholar
  27. J. Spencer and G. Tóth. Crossing numbers of random graphs. Random Structures Algorithms, 21:347-358, 2002. Google Scholar
  28. D. Spielman and S. H. Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51:385-463, 2004. Google Scholar
  29. B. Sudakov and J. Vondrák. How many random edges make a dense hypergraph non-2-colorable? Random Structures Algorithms, 32:290-306, 2008. Google Scholar
  30. T. Tao and V. Vu. The condition number of a randomly perturbed matrix. In STOC'07 - Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 248-255. ACM, New York, 2007. 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