The Multilevel Splitting algorithm for graph colouring with application to the Potts model

References

• R.B. Potts and C. Domb, Some generalized order-disorder transformations, Proc. Cambridge Philos. Soc. 48 (1952), p. 106.
   Web of Science ®Google Scholar
• M.I.D. Berganza, V. Loreto, and A. Petri, Phase ordering and symmetries of the potts model, Philos. Mag. 87 (2007), pp. 779–786.
   Web of Science ®Google Scholar
• F.Y. Wu, The Potts model, Rev. Mod. Phys. 54 (1982), pp. 235–268.
   Web of Science ®Google Scholar
• R.J. Baxter, Exactly solved models in statistical mechanics, Academic Press, London, 1982.
   Google Scholar
• D. Hu, P. Ronhovde, and Z. Nussinov, Phase transitions in random potts systems and the community detection problem: spin-glass type and dynamic perspectives, Philos. Mag. 92 (2012), pp. 406–445.
   Web of Science ®Google Scholar
• M. Jerrum and A. Sinclair, Polynomial-time approximation algorithms for the ising model, SIAM J. Comput. 22 (1993), pp. 1087–1116.
   Web of Science ®Google Scholar
• N. Alon, A.M. Frieze, and D. Welsh, Polynomial time randomized approximation schemes for tutte-gröthendieck invariants: The dense case, Random Struct. Algorithms 6 (1995), pp. 459–478.
   Web of Science ®Google Scholar
• F. Friedrich, A. Kempe, V. Liebscher, and G. Winkler, Complexity penalized M-Estimation: Fast computation, J. Comput. Graph. Statist. 17 (2008), pp. 201–224.
   Web of Science ®Google Scholar
• Y. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Trans. Pattern Anal. Mach. Intell. 23 (2001), pp. 1222–1239.
   Web of Science ®Google Scholar
• J. Voit, The Statistical Mechanics of Financial Markets, Applications of Mathematics, Springer, New York, 2001.
   Google Scholar
• F. Graner and J.A. Glazier, Simulation of biological cell sorting using a two-dimensional extended Potts model, Phys. Rev. Lett. 69 (1992), pp. 2013–2016.
   PubMed Web of Science ®Google Scholar
• C.I. Chou and S.P. Li, Spin systems and political districting problem, J. Magnetism Magnetic Mater. 310 (2007), pp. 2889–2891. Proceedings of the 17th International Conference on Magnetism.
   Web of Science ®Google Scholar
• M. Bordewich, C.S. Greenhill and V. Patel, Mixing of the Glauber dynamics for the ferromagnetic Potts model, Random Struct. Algor. 48 (2016), pp. 21–52.
   Google Scholar
• A.D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, in Surveys in Combinatorics, B.S. Webb, ed., Cambridge University Press, London, 2005, pp. 173–226.
   Google Scholar
• G.D. Birkhoff and D.C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), pp. 355–451.
   Web of Science ®Google Scholar
• R. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R. Miller and J. Thatcher, eds., Plenum Press, Boston, MA, 1972, pp. 85–103.
   Google Scholar
• L.G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8 (1979), pp. 410–421.
   Web of Science ®Google Scholar
• S.P. Vadhan, The complexity of counting in sparse, regular, and planar graphs, SIAM J. Comput. 31 (1997), pp. 398–427.
   Web of Science ®Google Scholar
• R.M. Karp and M. Luby, Monte-Carlo algorithms for enumeration and reliability problems, Proceedings of the 24th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1983, pp. 56–64.
   Google Scholar
• M. Dyer, Approximate counting by dynamic programming, Proceedings of the 35th ACM Symposium on Theory of Computing, ACM, San Diego, CA, 2003, pp. 693–699.
   Google Scholar
• M. Jerrum, A. Sinclair, and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, J. ACM 51(4) (2004), pp. 671–697.
   Web of Science ®Google Scholar
• M. Dyer, A. Frieze and M. Jerrum, On counting independent sets in sparse graphs, In 40th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, New York, NY, 1999, pp. 210–217.
   Google Scholar
• F. Jaeger, D.L. Vertigan, and D. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc. 108 (1990), pp. 35–53.
   Web of Science ®Google Scholar
• L.A. Goldberg and M. Jerrum, Inapproximability of the Tutte polynomial, Inform. Comput. 206 (2008), pp. 908–929.
   Web of Science ®Google Scholar
• M. Jerrum, L.G. Valiant, and V.V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theor. Comput. Sci. 43 (1986), pp. 169–188.
   Web of Science ®Google Scholar
• R.Y. Rubinstein, The Gibbs cloner for combinatorial optimization, counting and sampling, Methodology Comput. Appl. Probab. 11 (2009), pp. 491–549.
   Web of Science ®Google Scholar
• Z.I. Botev and D.P. Kroese, Efficient Monte Carlo simulation via the generalized splitting method, Statist. Comput. 22 (2012), pp. 1–16.
   Web of Science ®Google Scholar
• M. Jerrum and A. Sinclair, The Markov Chain Monte Carlo Method: An Approach To Approximate Counting And Integration, in Approximation Algorithms for NP-hard Problems, D. Hochbaum, ed., PWS Publishing, Boston, MA, 1996, pp. 482–520.
   Google Scholar
• R.Y. Rubinstein, A. Dolgin, and R. Vaisman, The splitting method for decision making, Commun. Statist. - Simulation Comput. 41 (2012), pp. 905–921.
   Web of Science ®Google Scholar
• J.K. Blitzstein and P. Diaconis, A sequential importance sampling algorithm for generating random graphs with prescribed degrees, Internet Math. 6 (2011), pp. 489–522.
   Google Scholar
• Y. Chen, P. Diaconis, S.P. Holmes, and J.S. Liu, Sequential Monte Carlo methods for statistical analysis of tables, J. Amer. Statist. Assoc. 100 (2005), pp. 109–120.
   Web of Science ®Google Scholar
• R.Y. Rubinstein, A. Ridder, and R. Vaisman, Fast Sequential Monte Carlo Methods for Counting and Optimization, Wiley Series in Probability and Statistics, John Wiley & Sons, New York, 2013.
   Google Scholar
• J. Blanchet and D. Rudoy, Rare Event Simulation and Counting Problems, in Rare Event Simulation Using Monte Carlo Methods [45], Wiley, 2009, pp. 171–192.
   Google Scholar
• H. Kahn and T.E. Harris, Estimation of particle transmission by random sampling, Nat. Bureau Standards Appl. Math. Ser. 12 (1951), pp. 27–30.
   Google Scholar
• V. Gogate and R. Dechter, Sampling-based lower bounds for counting queries, Intelligenza Artificiale 5 (2011), pp. 171–188.
   Google Scholar
• D.J. Watts and S.H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393 (1998), pp. 409–10.
   PubMed Web of Science ®Google Scholar
• M. Barthélémy and L.A.N. Amaral, Small-world networks: Evidence for a crossover picture, Phys. Rev. Lett. 82 (1999), pp. 3180–3183.
   Web of Science ®Google Scholar
• M. Humphries, K. Gurney, and T. Prescott, The brainstem reticular formation is a small-world, not scale-free, network, Proc. R. Soc. London B. 273 (2006), pp. 503–511.
   PubMed Web of Science ®Google Scholar
• Q.K. Telesford, K.E. Joyce, S. Hayasaka, J.H. Burdette, and P.J. Laurienti, The ubiquity of small-world networks, Brain Connectivity 1 (2011), pp. 367–375.
   PubMedGoogle Scholar
• P. Erdös and A. Rényi, On random graphs, I, Publicationes Math. (Debrecen) 6 (1959), pp. 290–297.
   Google Scholar
• E. Gilbert, Random graphs, Ann. Math. Statist. 30 (1959), pp. 1441–1144.
   Google Scholar
• D.J.A. Welsh and C. Merino, The potts model and the tutte polynomial, J. Math. Phys. 41 (2000), pp. 1127–1152.
   Web of Science ®Google Scholar
• J. Salas and A.D. Sokal, Transfer matrices and partition-function zeros for antiferromagnetic potts models. I. General theory and square-lattice chromatic polynomial, J. Statist. Phys. 104 (2001), pp. 609–699.
   Web of Science ®Google Scholar
• P.T.D. Boer, D.P. Kroese, S. Mannor, and R.Y. Rubinstein, A tutorial on the cross-entropy method, Ann. Oper. Res. 134 (2002), pp. 19–67.
   Web of Science ®Google Scholar
• G. Rubino and B. Tuffin, Rare Event Simulation Using Monte Carlo Methods, John Wiley & Sons, West Sussex, UK, 2009.
   Google Scholar
• R.Y. Rubinstein and D.P. Kroese, Simulation and the Monte Carlo Method, Wiley Series in Probability and Statistics. 2nd ed., John Wiley & Sons, New York, 2008.
   Google Scholar
• O. Strichman, in Efficient Decision Procedures for Validation: Translation Validation, Decision Procedures for Equality Logic, and SAT Tuning for Bounded Model Checking, LAP Lambert Academy Publications, Saarbrucken, Germany, 2009.
   Google Scholar
• F. Cérou, A. Guyader, R.Y. Rubinstein, and R. Vaisman, On the use of smoothing to improve the performance of the splitting method, Stochast. Models 27 (2011), pp. 629–650.
   Web of Science ®Google Scholar
• E.M. Stein and R. Shakarchi, Real analysis : measure theory, integration, and Hilbert spaces, Princeton lectures in analysis. Princeton University Press, Princeton (NJ), Oxford, 2005.
   Google Scholar
• J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combinatorics 16 (2008), pp. 1–58.
   Google Scholar
• G. Haggard, D.J. Pearce, and G. Royle, Computing Tutte polynomials, ACM Trans. Math. Softw. 37 (2010), pp. 24:1–24:17.
   Google Scholar
• A. Coja-Oghlan, K. Panagiotou, and A. Steger, On the chromatic number of random graphs, J. Combinatorial Theory Ser. B 98 (2008), pp. 980–993.
   Web of Science ®Google Scholar