Abstract
The paper presents the use of reinforcement learning in edge coloring of a complete graph, and more specifically in the problem of determining Ramsey numbers. To the best of our knowledge, no one has so far dealt with the use of RL techniques for graph edge coloring.
The paper contains an adaptation of the method of Zhou et al. to the problem of finding specific Ramsey colorings. The proposed algorithm was tested by successfully finding critical colorings for selected known Ramsey numbers. The results of proposed algorithm are so promising that we may have a chance to find unknown Ramsey numbers.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Bengio, Y., Lodi, A., Prouvost, A.: Machine learning for combinatorial optimization: a methodological tour d’horizon. Eur. J. Oper. Res. 290(2), 405–421 (2021)
Brandt, S.: A sufficient condition for all short cycles. Discret. Appl. Math. 79, 63–66 (1997)
Caccetta, L., Vijayan, K.: Maximal cycles in graphs. Discret. Math. 98, 1–7 (1991)
Ceberio, J., Mendiburu, A., Lozano, J. A.: The Plackett-Luce ranking model on permutation-based optimization problems. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC), pp. 494–501. IEEE, Cancun (2013)
Faudree, R.J., Lesniak, L., Schiermeyer, I.: On the circumference of a graph and its complement. Discret. Math. 309, 5891–5893 (2009)
Faudree, R.J., Schelp, R.H.: All Ramsey numbers for cycles in graphs. Discret. Math. 8, 313–329 (1974)
Frederickson, G., Lynch, N.: Electing a leader in a synchronous ring. J. Assoc. Comput. Mach. 34, 98–115 (1987)
Greenwood, R.E., Gleason, A.M.: Combinatorial relations and chromatic graphs. Can. J. Math. 7, 1–7 (1955)
McKay, B.D., Radziszowski, S.P.: \(R (4, 5) = 25\). J. Graph Theory 19, 309–322 (1995)
Radziszowski, S.: Small Ramsey numbers. Electron. J. Combin. (2021). Dynamic Survey 1, revision 16
Rosta, V.: Ramsey Theory Applications. Electron. J. Combin. (2004). Dynamic Survey 13
Rosta, V.: On a Ramsey type problem of J.A. Bondy and P. Erdoös, I & II. J. Combin. Theory Ser. B 15, 94–120 (1973)
Snir, M.: On parallel searching. SIAM J. Comput. 14, 688–708 (1985)
Yow, K.S., Luo, S.: Learning-based approaches for graph problems: a survey. https://arxiv.org/abs/2204.01057. Accessed 4 Jan 2022
Zhang, Y., Broersma, H., Chen, Y.: Narrowing down the gap on cycle-star Ramsey numbers. J. Combin. 7(2–3), 481–493 (2016)
Zhou, Y., Hao, J.-K., Duval, B.: Reinforcement learning based local search for grouping problems: a case study on graph coloring. Expert Syst. Appl. 64, 412–422 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Dzido, T. (2023). Applying Reinforcement Learning to Ramsey Problems. In: Mikyška, J., de Mulatier, C., Paszynski, M., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M. (eds) Computational Science – ICCS 2023. ICCS 2023. Lecture Notes in Computer Science, vol 10476. Springer, Cham. https://doi.org/10.1007/978-3-031-36027-5_46
Download citation
DOI: https://doi.org/10.1007/978-3-031-36027-5_46
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-36026-8
Online ISBN: 978-3-031-36027-5
eBook Packages: Computer ScienceComputer Science (R0)