Top

previous chapter Weighted Random Sampling over Data Streams

next chapter A Selective Tour Through Congestion Games

Hint

Swipe to navigate through the chapters of this book

2015 | OriginalPaper | Chapter

Random Instances of Problems in NP – Algorithms and Statistical Physics

Read first chapter

Author: Charilaos Efthymiou

Publisher: Springer International Publishing

Published in: Algorithms, Probability, Networks, and Games

» Get access to the full-text

Abstract

One of the most intriguing discoveries made by Erdös and Rényi in the course of their investigating random graphs is the so-called phase transition phenomenona, like the sudden emergence of the giant component. Since then, this kind of phenomena have been observed in many, diverse, areas of combinatorics and discrete mathematics in general. Typically, the notion of phase transition in combinatorics is related to a sudden change in the structural properties of a combinatorial construction, e.g. a (hyper)graph, arithmetic progressions e.t.c. However, it seems that the study of phase transitions goes much further. There is an empirical evidence that certain phase transition phenomena play a prominent role in the performance of algorithms for a lot of natural computational problems. That is, phase transitions are related to the, somehow elusive, notion of computational intractability. The last fifteen-twenty years, there has been serious attempts to put this relation on a mathematically rigorous basis. Our aim is to highlight some of the most central problems that arise in this endeavor.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

As local greedy algorithms.

The interested reader can find rapid mixing bound fro the hard-core model (weighted independent sets), too.

The paper in [ 31] is for G( n, p) model for \(p=d/n\), the result for G( n, m) follow by using standard arguments.

There are cases where the dynamics remains ergodic beyond non-reconstruction, e.g. hard-core model. In these cases the non-ergodicity is substituted by “low conductance”, which implies slow mixing.

Since this search usually gets stuck in a local but not a global optimum, it is customary to carry out the process several times, starting from different configurations, and save the best result.

Independent set of a graph is any subset of its vertices which do not span any edge with each other.

Somehow the problem of computing marginals turns out to be easier than sampling.

The algorithm in [ 30] is for the related G( n, p) where \(p=d/n\). result for G( n, m) follows by just using standard arguments.

To be more precise the colour remains asymptotically random.

This justifies the name message passing algorithm.

Achlioptas, D., Coja-Oghlan, A.: Algorithmic Barriers from Phase Transitions. In: Proceedings of 49th IEEE Symposium on Foundations of Computer Science, FOCS (2008)

Achlioptas, D., Coja-Oghlan, A., Ricci-Tersenghi, F.: On the solution-space geometry of random constraint satisfaction problems. Random Struct. Algorithms 38(3), 251–268 (2011) MathSciNetCrossRefMATH

Achlioptas, D., Friedgut, E.: A sharp threshold for \(k\)-colorability. Random Struct. Algorithms 14(1), 63–70 (1999) MathSciNetCrossRefMATH

Achlioptas, D., Moore, C.: Random \(k\)-SAT: two moments suffice to cross a sharp threshold. SIAM J. Comput. 36(3), 740–762 (2006) MathSciNetCrossRefMATH

Achlioptas, D., Naor, A.: The two possible values of the chromatic number of a random graph. Ann. Math. 162(3), 1333–1349 (2005) MathSciNetCrossRefMATH

Achlioptas, D., Peres, Y.: The threshold for random \(k\)-SAT is \(2^k \log 2 - O(k)\). J. AMS 17, 947–973 (2004) MathSciNetMATH

Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. In: Proceedings of 9th ACM-SIAM Symposium on Discrete Algorithms, SODA 1998 (1998)

Bapst, V., Coja-Oghlan, A., Hetterich, S., Rassmann, F., Vilenchik, D.: The condensation phase transition in random graph coloring. In: proceedings of APPROX-RANDOM 2014, pp. 449–464 (2014)

van den Berg, J., Maes, C.: Disagreement percolation in the study of Markov fields. Ann. Probab. 22, 749–763 (1994) MathSciNetCrossRefMATH

10.

Bhatnagar, N., Sly, A., Tetali, P.: Decay of Correlations for the Hardcore Model on the \(d\)-regular Random Graph. http://arxiv.org/abs/1405.6160

11.

Braunstein, A., Mézard, A., Zecchina, R.: Survey propagation: an algorithm for satisfiability. Random Struct. Algorithms 27, 201–226 (2004) MathSciNetCrossRefMATH

12.

Brightwell, G., Winkler, P.: A second threshold for the hard-core model on a Bethe lattice. Random Struct. Algorithms 24, 303–314 (2004) MathSciNetCrossRefMATH

13.

Bubley, R., Dyer, M.: Path coupling: a technique for proving rapid mixing in markov chains. In: proceedings of 38th FOCS, pp 223–231 (1997)

14.

Coja-Oghlan, A.: A Better Algorithm for Random \(k\)-SAT. In: proceedings of ICALP (1) 2009: 292–303. SIAM J. Comput. 39(7) 2823–2864 (2010)

15.

Coja-Oghlan, A.: The asymptotic \(k\)-SAT threshold. In: proceedings of STOC 2014: 804–813 (2014)

16.

Coja-Oghlan, A., Efthymiou, C.: On independent sets in Random Graphs. In: Proceedings of 22nd ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp 136–144 (2011)

17.

Coja-Oghlan, A., Efthymiou, C., Hetterich, S.: On the chromatic number of random regular graphs. http://arxiv.org/abs/1308.4287

18.

Coja-Oghlan, A., Efthymiou, C., Jaafari, N.: Local convergence of random graph colorings. http://arxiv.org/abs/1501.06301

19.

Coja-Oghlan, A., Panagiotou, K.: Going after the k-SAT threshold. In: procedings of STOC 2013: 705–714 (2013)

20.

Coja-Oghlan, A., Panagiotou, K.: Catching the k-NAESAT threshold. In: proceedings of STOC 2012: 899–908 (2012)

21.

Coja-Oghlan, A., Vilenchik, D.: Chasing the k-colorability threshold. In: Proceedings of 54th IEEE Symposium on Foundations of Computer Science, FOCS 2013, pp 380–389 (2013)

22.

Chvátal, V., Reed, B.: Mick gets some (the odds are on his side). In: Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pp. 620–627 (1992)

23.

Dani, V., Moore, C.: Independent sets in random graphs from the weighted second moment method. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) RANDOM 2011 and APPROX 2011. LNCS, vol. 6845, pp. 472–482. Springer, Heidelberg (2011) CrossRef

24.

Ding, J., Sly, A., Sun, N.: Maximum independent sets on random regular graphs. http://arxiv.org/abs/1310.4787

25.

Ding, J., Sly, A., Sun, N.: Satisfiability threshold for random regular NAE-SAT. In: proceendings of STOC 2014: 814–822 (2014)

26.

Ding, J., Sly, A., Sun, N.: Proof of the satisfiability conjecture for large \(k\). To appear in STOC 2015 (2015)

27.

Dyer, M., Flaxman, A., Frieze, A.M., Vigoda, E.: Random colouring sparse random graphs with fewer colours than the maximum degree. Random Struct. Algorithms 29, 450–465 (2006) CrossRefMATH

28.

Dyer, M.E., Frieze, A.M.: The solution of some random np-hard problems in polynomial expected time. J. Algorithms 10(4), 451–489 (1989) MathSciNetCrossRefMATH

29.

Dyer, M., Frieze, A.M., Hayes, A., Vigoda, E.: Randomly colouring constant degree graphs. In proceedings of 45th FOCS, pp 582–589 (2004)

30.

Efthymiou, C.: A simple algorithm for random colouring \(G(n, d/n)\) using \((2 + \epsilon )d\) colours. In: Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 (2012)

31.

Efthymiou, C.: MCMC sampling colourings and independent sets of G(n, d/n) near the uniqueness threshold. In: proceedings of Symposium on Discrete Algorithms, SODA (2014)

32.

Efthymiou, C.: Switching colouring of G( n, d/ n) for sampling up to gibbs uniqueness threshold. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 371–381. Springer, Heidelberg (2014)

33.

Efthymiou, C.: Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees. CoRR abs/1406.3617 (2014)

34.

Freeman, W.T., Paztor, E.C., Carmichael, O.T.: Learning low-level vision. Int. J. Comput. Vis. 40, 25–47 (2000) CrossRefMATH

35.

Friedgut, E.: Necessary and sufficient conditions for sharp thresholds of graph properties, and the k-SAT problem. J. Amer. Math. Soc. 12, 1017–1054 (1999) MathSciNetCrossRefMATH

36.

Frieze, A.M.: On the independence number of random graphs. Discrete Math. 81(183), 171–175 (1990) MathSciNetCrossRefMATH

37.

Frieze, A.M., Vera, J.: On randomly colouring locally sparse graphs. Discrete Math. & Theor. Comput. Sci. 8(1), 121–128 (2006) MathSciNetMATH

38.

Georgii, H.O.: Gibbs Measures and Phase Transitions, de Gruyter Stud. Math. 9, de Gruyter, Berlin (1988)

39.

Goldberg, L.A., Martin, R.A., Paterson, M.: Strong spatial mixing with fewer colors for lattice graphs. SIAM J. Comput. 35(2), 486–517 (2005) MathSciNetCrossRefMATH

40.

Grimmett, G.R., McDiarmid, C.J.H.: On colouring random graphs. Math. Proc. Camb. Phil. Soc. 77(02), 313–332 (1975) MathSciNetCrossRefMATH

41.

Hayes, T., Vera, J., Vigoda, E.: Randomly coloring planar graphs with fewer colors than the maximum degree. In: proceedings of 39th STOC, pp 450–458 (2007)

42.

Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18(6), 1138–1162 (1970) MathSciNetCrossRefMATH

43.

Jerrum, M.R.: Large cliques elude the Metropolis process. Random Struct. Algorithms 3, 347–359 (1992) MathSciNetCrossRefMATH

44.

Jerrum, M.R., Sinclair, A.: The Markov chain Monte Carlo method: an approach to approximate counting and integration. In: Approximation Algorithms for NP-hard Problems, (Dorit Hochbaum, ed.), PWS (1996)

45.

Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. J. ACM 51(4), 671–697 (2004) MathSciNetCrossRefMATH

46.

Karp, R., Sipser, M.: Maximum matchings in sparse random graphs. In: proceedings of FOCS 1981, pp. 364 375 (1981)

47.

Kelly, F.P.: Loss networks. Ann. Appl. Probab. 1(3), 319–378 (1991) MathSciNetCrossRefMATH

48.

Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimisation by simulated annealing. Science 220, 671–680 (1983) MathSciNetCrossRefMATH

49.

Kirousis, L.M., Kranakis, E., Krizanc, D., Stamatiou, Y.C.: Approximating the unsatisfiability threshold of random formulas. Random Struct. Algor. 12(3), 253–269 (1998) MathSciNetCrossRefMATH

50.

Krzakala, F., Montanari, A., Ricci-Tersenghi, F., Semerjianc, G., Zdeborova, L.: Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci. 104, 10318–10323 (2007) MathSciNetCrossRefMATH

51.

Kschischang, F., Frey, B., Loeliger, H.A.: Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory 47, 498519 (2001) MathSciNetCrossRefMATH

52.

Levin, D., Peres, Y., Wilmer, E.: Markov Chains and Mixing Times. American Mathematical Society (2008)

53.

Lovász, L., Vempala, S.: Simulated annealing in convex bodies and an \(O*(n^4)\) volume algorithm. In: Proceedings of the 44th IEEE Foundations of Computer Science (FOCS 2003) (2003). Also in JCSS (FOCS 2003 special issue)

54.

Lucier, B., Molloy, M., Peres, Y.: The Glauber Dynamics for Colourings of Bounded Degree Trees. In: proceedings of RANDOM 2009, pp 631–645 (2009)

55.

Martinelli, F., Sinclair, A., Weitz, D.: Fast mixing for independent sets, colorings and other models on trees. In: proceedings of 15th SODA, pp 456–465 (2004)

56.

Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21, 1087–1092 (1953) CrossRef

57.

Mézard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science 297(5582), 812–815 (2002) CrossRef

58.

Molloy, M.: The Glauber dynamics on the colourings of a graph with large girth and maximum degree. SIAM J. Comput. 33, 721–737 (2004) MathSciNetCrossRefMATH

59.

Montanari, A., Restrepo, R., Tetali, P.: Reconstruction and clustering in random constraint satisfaction problems. SIAM J. Discrete Math. 25(2), 771–808 (2011) MathSciNetCrossRefMATH

60.

Montanari, A., Shah, D.: Counting good truth assignments of random \(k\)-SAT formulae. In: proceedings of the 18th Annual ACM-SIAM, SODA 2007, pp 1255–1264 (2007)

61.

Mossel, E., Sly, A.: Gibbs rapidly samples colorings of \(G_{n, d/n}\). J. Probab. Theory Relat. fields 148, 1–2 (2010) CrossRefMATH

62.

Pearl, J.: Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan-Kaufmann, Palo Alto (1988) MATH

63.

Restrepo, R., Stefankovic, D., Vera, J.C., Vigoda, E., Yang, L.: Phase transition for glauber dynamics for independent sets on regular trees. In: proceedings SODA 2011, pp 945–956 (2011)

64.

Richardson, T., Urbanke, R.: The capacity of low-density parity check codes under message passing deconding. IEEE Trans. Inf. Theory 47, 599–618 (2001) CrossRefMATH

65.

Schöning, U.: A probabilistic algorithm for \(k\)-SAT and constraint satisfaction problems. In: proceedings of Symposium on Foundations of Computer Science, FOCS 1999, pp 410–419 (1999)

66.

Tetali, P., Vera, J.C., Vigoda, E., Yang, L.: Phase transition for the mixing time of the glauber dynamics for coloring regular trees. In: proceedings of SODA 2010, pp 1646–1656 (2010)

67.

Vigoda, E.: Improved bounds for sampling colorings. J. Math. Phys. 41(3), 1555–1569 (2000). A preliminary version appears in FOCS 1999 MathSciNetCrossRefMATH

Title

Random Instances of Problems in NP – Algorithms and Statistical Physics

Book

Algorithms, Probability, Networks, and Games

Print ISBN: 978-3-319-24023-7

Electronic ISBN: 978-3-319-24024-4

https://doi.org/10.1007/978-3-319-24024-4

DOI

https://doi.org/10.1007/978-3-319-24024-4_13

Author:

Charilaos Efthymiou

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits