Tackling the maximum happy vertices problem in large networks. (English) Zbl 1462.68148
Summary: In this paper we consider a variant of graph colouring known as the maximum happy vertices problem. This problem involves taking a graph in which a subset of the vertices have been preassigned to colours. The objective is to then colour the remaining vertices such that the number of happy vertices is maximised, where a vertex is considered happy only when it is assigned to the same colour as all of its neighbours. We design and test a tabu search approach, which is compared to two existing state of the art methods. We see that this new approach is particularly suited to larger problem instances and finds very good solutions in very short time frames. We also propose a algorithm to find upper bounds for the problem efficiently. Moreover, we propose an algorithm for imposing additional precoloured vertices and are hence able to significantly reduce the solution space. Finally, we present an analysis of this problem and use probabilistic arguments to characterise problem hardness.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68W40 | Analysis of algorithms |
References:
| [1] | Agrawal A, (2018) On the parameterized complexity of happy vertex coloring. In: Brankovic L, Ryan J, Smyth W (eds) Combinatorial algorithms. IWOCA, (2017) Lecture notes in computer science, vol 10765. Springer, Cham, pp 103-115 · Zbl 1454.68087 |
| [2] | Aravind, N.; Kalyanasundaram, S.; Kare, A.; Mäkinen, V.; Puglisi, S.; Salmela, L., Linear time algorithms for happy vertex coloring problems for trees, Combinatorial algorithms. IWOCA 2016. Lecture notes in computer science, 281-292 (2016), Cham: Springer, Cham · Zbl 1454.68092 |
| [3] | Barabási, AL; Põsfai, M., Network science (2016), Cambridge: Cambridge University Press, Cambridge · Zbl 1353.94001 |
| [4] | Blöchliger, I.; Zufferey, N., A graph coloring heuristic using partial solutions and a reactive tabu scheme, Computers & Operations Research, 35, 3, 960-975 (2008) · Zbl 1278.90327 · doi:10.1016/j.cor.2006.05.014 |
| [5] | Blum, C.; Roli, A., Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM Comput Surv, 35, 268-308 (2003) · doi:10.1145/937503.937505 |
| [6] | Carter, MW; Laporte, G.; Lee, SY, Examination timetabling: algorithmic strategies and applications, J Oper Res Soc, 47, 3, 373-383 (1996) · doi:10.1057/jors.1996.37 |
| [7] | Di Gaspero, L.; Schaerf, A.; Burke, E.; Erben, W., Tabu search techniques for examination timetabling, Practice and theory of automated timetabling III, 104-117 (2001), Berlin: Springer, Berlin · Zbl 0982.68784 · doi:10.1007/3-540-44629-X_7 |
| [8] | Everitt, B.; Landau, S.; Leese, M.; Stahl, D., Cluster analysis (2011), Hoboken: Wiley, Hoboken · Zbl 1274.62003 · doi:10.1002/9780470977811 |
| [9] | Glover, F.; Laguna, M., Tabu search (1997), Norwell: Kluwer Academic Publishers, Norwell · Zbl 0930.90083 · doi:10.1007/978-1-4615-6089-0 |
| [10] | Glover, F.; Laguna, M., Tabu search, 2093-2229 (1999), Boston: Springer, Boston |
| [11] | Lewis, R., A guide to graph colouring: algorithms and applications (2015), Berlin: Springer, Berlin |
| [12] | Lewis R (2020) Tabu search source code. http://www.rhydlewis.eu/resources/happytabu.zip. Accessed 24 Jan 2020 |
| [13] | Lewis, R.; Carroll, F., Creating seating plans: a practical application, J Oper Res Soc, 67, 11, 1353-1362 (2016) · doi:10.1057/jors.2016.34 |
| [14] | Lewis, R.; Thompson, J., Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem, Eur J Oper Res, 240, 3, 637-648 (2015) · Zbl 1338.90172 · doi:10.1016/j.ejor.2014.07.041 |
| [15] | Lewis, R.; Thiruvady, D.; Morgan, K., Finding happiness: an analysis of the maximum happy vertices problem, Comput Oper Res, 103, 265-276 (2019) · Zbl 1458.05076 · doi:10.1016/j.cor.2018.11.015 |
| [16] | Li, A.; Zhang, P., Algorithmic aspects of homophyly of networks, Theor Comput Sci, 593, 117-131 (2015) · Zbl 1330.68127 · doi:10.1016/j.tcs.2015.06.003 |
| [17] | Mabrouk, BB; Hasni, H.; Mahjoub, Z., On a parallel genetic-tabu search based algorithm for solving the graph colouring problem, Eur J Oper Res, 197, 3, 1192-1201 (2009) · Zbl 1176.90482 · doi:10.1016/j.ejor.2008.03.050 |
| [18] | McCollum, B.; Schaerf, A.; Paechter, B.; McMullan, P.; Lewis, R.; Parkes, AJ; Gaspero, L.; Qu, R.; Burke, EK, Setting the research agenda in automated timetabling: the second international timetabling competition, INFORMS J Comput, 22, 1, 120-130 (2010) · Zbl 1243.90007 · doi:10.1287/ijoc.1090.0320 |
| [19] | Zhang, P.; Xu, Y.; Jiang, T.; Li, A.; Lin, G.; Miyano, E., Improved approximation algorithms for the maximum happy vertices and edges problems, Algorithmica, 80, 5, 1412-1438 (2018) · Zbl 1387.68301 · doi:10.1007/s00453-017-0302-8 |
| [20] | Zufferey, N.; Amstutz, P.; Giaccari, P., Graph colouring approaches for a satellite range scheduling problem, J Sched, 11, 4, 263-277 (2008) · Zbl 1168.90481 · doi:10.1007/s10951-008-0066-8 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
